Valid Parenthesis String — Step-by-Step Visualization

Algorithm Pattern

Greedy Bi-directional Bounds

Key Idea

A simple count won't work because `*` has three possibilities. Instead, we track the RANGE of possible open brackets `[leftMin, leftMax]`. When we see '(', both min and max increase. When we see ')', both decrease. When we see '*', the range widens: min decreases (treat as closing) and max increases (treat as opening). If `leftMax` ever drops below 0, it's impossible. If `leftMin` drops below 0, reset it to 0 because we can't have negative brackets. Finally, `leftMin == 0` must be possible.

Step-by-Step Approach

1. Initialize `leftMin = 0`, `leftMax = 0`.
2. Iterate through the string.
3. If '(': `leftMin++`, `leftMax++`.
4. If ')': `leftMin--`, `leftMax--`.
5. If '*': `leftMin--`, `leftMax++`.
6. If `leftMax < 0`, return `False`.
7. If `leftMin < 0`, `leftMin = 0`.
8. After loop, return `leftMin == 0`.

Common Gotchas

• The 'min' count can't go below 0 during iteration because we can always treat some '*' as empty strings instead of closing brackets.
• A negative `leftMax` means even if we treat all '*' as opening brackets, we still have too many closing brackets at that point.