# LeetCode 678: Valid Parenthesis String — Step-by-Step Visual Trace

**Medium** — String | Greedy | Stack

## The Problem

Determine if a string containing parentheses '(', ')', and wildcards '*' is valid, where '*' can represent '(', ')', or an empty string.

## Approach

Use a greedy approach by tracking the minimum and maximum possible count of open parentheses. For each character, update the bounds and check if a valid configuration exists.

**Time:** O(n) · **Space:** O(1)

## Code

```python
class Solution:
    def checkValidString(self, s: str) -> bool:
        lower = upper = 0

        for char in s:
            if char == "(":
                lower += 1
                upper += 1
            elif char == ")":
                lower = max(lower - 1, 0)
                upper -= 1
            else:  # char == '*'
                lower = max(lower - 1, 0)
                upper += 1

            if upper < 0:
                return False

        return lower == 0
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0678_valid-parenthesis-string)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0678_valid-parenthesis-string) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*