Valid Parenthesis String (LeetCode 678) Solution

The problem

You get a string of (, ) and *. Each * can act as (, as ), or as nothing. Return True if some choice for the stars makes the string a valid bracket sequence: every ) closes an earlier ( and nothing is left open at the end.

Input:  s = "(*))"
Output: True

Treat the * as ( and you get (()), which is balanced. By contrast "(((*)" is False: even if the star closes one bracket, two ( stay open.

How to think about it

Start with brute force. Try all three meanings for every star and check each resulting string. With k stars that is 3ᵏ strings. A DP over (index, open count) brings it down to O(n²), but there is something simpler.

Recall the no-star version. Without stars you keep one counter, the number of open brackets. ( adds one, ) subtracts one. The string is valid if the counter never goes negative and ends at 0.

The key insight: with stars, the counter becomes a range. You don’t know which value the open count has, but you know the set of possible values is a contiguous range [lo, hi]. ( shifts both ends up. ) shifts both down. * could do either, so lo goes down and hi goes up. Two rules keep the range honest:

If hi < 0, even treating every star as ( leaves too many ). Fail now.
Clamp lo at 0. A negative open count is never a legal state, so the choices that produced it are dropped.

At the end the string is valid if 0 is in the range, which (since lo >= 0) means lo == 0.

Which pattern is this? Greedy state compression: instead of tracking every branch, track only the bounds of what is possible. The tell is “wildcards in a bracket check”.

Approach

Set lo = hi = 0.
For each character: ( adds 1 to both; ) subtracts 1 from both; * subtracts 1 from lo and adds 1 to hi.
If hi < 0, return False.
Set lo = max(lo, 0).
After the scan, return lo == 0.

Solution

def check_valid_string(s):
    lo = hi = 0                       # min and max possible number of open brackets
    for c in s:
        if c == '(': lo += 1; hi += 1
        elif c == ')': lo -= 1; hi -= 1
        else: lo -= 1; hi += 1        # '*' widens the range both ways
        if hi < 0: return False       # too many ')' even if every '*' is '('
        lo = max(lo, 0)               # a negative open count is impossible
    return lo == 0
# check_valid_string("(*))") -> True
# check_valid_string("(((*)") -> False

Dry run

On "(*))":

char	`lo` before clamp	`lo`	`hi`
(	1	1	1
*	0	0	2
)	−1	0	1
)	−1	0	0

hi never went negative and lo == 0, so True. On "(((*)" the scan ends with lo = 1, hi = 3. Zero isn’t reachable, so False.

Complexity

Time: O(n). One pass, constant work per character.
Space: O(1). Two integers.

Edge cases and pitfalls

Empty string is valid: lo stays 0.
")(" fails on the first character, since hi drops to −1.
"*" alone is valid (treat it as empty).
Forgetting the clamp lets lo go negative and borrow from the future. Without it, "*(" ends with lo = 0 and wrongly passes; with it, lo ends at 1 and the answer is False.
Counting stars separately (“are there enough stars to fix the imbalance?”) ignores order. A * after a ) can’t rescue it.

Valid Parentheses (LeetCode 20): the base check this problem extends.
Generate Parentheses (LeetCode 22): uses the same open-count invariant to build only valid strings.
Regular Expression Matching (LeetCode 10): wildcards again, where a full DP really is needed.