Valid Parenthesis String
A string contains (, ), and , where may act as (, ), or an empty string. Return whether the string can be made valid.
Intuition
Without wildcards a single counter suffices, and reaching for one here is the natural mistake — after ( the open count could be 0, 1, or 2 at the same time, so any single number you commit to will be wrong later. Track the range instead: low assumes every star is the least helpful choice, high the most. The string is valid if that range can land on zero. One detail carries the whole thing: clamp low at 0, because an open-bracket count cannot go negative, and without the clamp valid strings like () fail.
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
See why one counter is not enough
Reading (* , the number of open brackets could be 0, 1, or 2 depending on how the star is used. A single counter must commit to one value and will be wrong later. Recursing over the three choices per star is O(3^n), and memoising it gives an O(n^2) DP that works but is far more code than needed.
Track an interval instead
Let low be the count if every star so far were a closing bracket, and high the count if every star were an opening one. A ( raises both, a ) lowers both, and a * lowers low and raises high — widening the range by one in each direction. Every achievable count lies between them.
Clamp low, fail on high, and check the end
If high ever goes negative there are too many closers even in the most generous reading, so return false immediately. If low goes negative, clamp it to 0 — a count of open brackets can never be negative, and the stars responsible can simply be treated as empty instead. At the end return low == 0, meaning some assignment closes every bracket exactly. One pass, O(n) time, O(1) space.
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.