Valid Parenthesis String
A string contains (, ), and **, where ** may act as (, ), or an empty string. Return whether the string can be made valid.
- 1 <= s.length <= 100
- s[i] is '(', ')' or '*'.
Intuition
Valid parenthesis string adds a wildcard * that can act as (, as ), or as an empty string. That flexibility breaks the plain stack solution, since a * cannot be classified when it is read.
Trying all three interpretations at each * is 3ⁿ. The efficient approach tracks a range of possible open-bracket counts rather than a single value:
- Maintain low and high — the fewest and most unclosed brackets possible given the choices so far — and the string is valid if zero stays within that range.
On (, both bounds increase. On ), both decrease. On *, low decreases and high increases, since the wildcard could be either bracket.
Two rules keep the range meaningful.
low must never drop below zero. A negative count is impossible, and letting it go negative allows later brackets to be closed against imaginary openings. Clamping it at zero is essential.
If high goes negative, the string is invalid immediately — even the most generous interpretation has more closings than openings, and no later character can repair it.
At the end, the string is valid when low is zero. A non-zero low means unclosed brackets remain under every interpretation.
The greedy is not obvious, and its correctness rests on the range being contiguous — every count between low and high is achievable, so checking the bounds suffices.
A two-pass alternative scans left to right treating * as (, then right to left treating it as ). Both must pass. Equally valid and easier to reason about.
One pass gives O(n) time and O(1) space.
Track a range of possible open-bracket counts rather than one number. A * widens the range in both directions; low clamps at zero because a wildcard can always be spent as an empty string. Valid means zero stays inside the range at the end.
Approach
Before reading on: price up what counting everything costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n) time and O(1) space.
See why the stack fails
A * cannot be classified when read — it may be an opening, a closing, or nothing. Trying all three interpretations is exponential.
Track a range of open counts
Keep low and high as the fewest and most unclosed brackets possible. Every count between them is achievable, which is what makes the bounds sufficient.
Update both bounds per character
( raises both, ) lowers both, and * lowers low while raising high — covering all three of its meanings at once.
Clamp low at zero
A negative open count is impossible. Letting low go negative lets later brackets close against openings that never existed.
Fail immediately on negative high
If high drops below zero, no interpretation works — even the most generous has excess closings, and no later character can repair it.
Require low to end at zero
The string is valid exactly when low is 0 at the end. A positive low means unclosed brackets under every interpretation.
Cost of the approach
One pass with two counters gives O(n) time and O(1) space, against 3^n for trying every wildcard assignment.
Solution & live demo
Common pitfalls
Letting low go negative
low -= 1
low = max(low, 0)
A negative low implies more closers than openers on some interpretation, but that interpretation simply isn't chosen — the wildcards absorb it. Without the clamp, valid strings like "(*)" are rejected.
Checking low < 0 as a failure
if low < 0: return False
if high < 0: return False
Failure means no interpretation works, which is exactly high < 0 — even treating every wildcard as an opener leaves unmatched closers. low going negative is recoverable, high is not.
Returning low <= 0
return low <= 0
return low == 0
Since low is clamped at zero it can never be negative, so <= 0 is the same test written misleadingly — but the real requirement is that a balanced interpretation exists, meaning low has actually reached 0 rather than merely being non-positive by clamping. Stating == 0 keeps the intent exact.
Edge cases
Every star can be empty, so low stays clamped at 0 and the answer is true.
high goes negative on the first character, returning false at once.
low drifts negative and the final low == 0 test fails on valid strings like "(*)".
low ends above 0, so no assignment balances the string and false is correct.