Valid Parenthesis String

Valid Parenthesis String adds a wildcard to the classic balanced-parentheses problem. The * can be one of three things, which seems to explode into too many cases — until you stop tracking a single open count and start tracking a range of possible open counts.

The slow way first

The brute-force idea: every * has 3 choices, so try all of them and check each resulting string for balance. With k stars that is 3ᵏ strings — exponential, hopeless for a long input.

The question to ask: do I really need to commit to what each * is? No. While scanning left to right, the only thing that matters for validity is how many open parens are currently unmatched. Because * is flexible, that count is not a single number — it is a range.

The idea: track lo and hi

Walk the string once, keeping two numbers:

• lo — the smallest number of open parens still possible (assume every * so far closed or vanished).
• hi — the largest number of open parens still possible (assume every * so far opened).

For each character: ( pushes both up, ) pulls both down, and * widens the range (lo - 1, hi + 1). If lo dips below 0 we clamp it to 0 — a * we were reading as ) can simply be read as empty instead. If hi ever goes negative there are flat-out too many ) and we fail. At the end, the string is valid exactly when lo can be 0.

The key insight: clamping lo at 0 lets the wildcards quietly "undo" an over-eager close, while hi going negative is the hard limit no choice of * can rescue.

Walk through it

Step through the animation on s = '(*))'. The pointer c scans left to right while lo and hi update beneath it. Watch lo try to go negative twice and get clamped back to 0 — that clamp is the whole trick. At the end lo == 0, so the answer is true.

Pseudocode

lo = 0          # fewest open parens still possible
hi = 0          # most open parens still possible
for each char c in s:
    if c == '(':  lo += 1; hi += 1
    elif c == ')': lo -= 1; hi -= 1
    else:          lo -= 1; hi += 1   # the wildcard widens the range
    if lo < 0: lo = 0                 # a '*' read as ')' can be empty instead
    if hi < 0: return False           # too many ')', no choice saves it
return lo == 0                        # valid iff 0 open is reachable

The Python solution

def check_valid_string(s):
    lo = 0
    hi = 0
    for c in s:
        if c == '(':
            lo += 1
            hi += 1
        elif c == ')':
            lo -= 1
            hi -= 1
        else:
            lo -= 1
            hi += 1
        if lo < 0:
            lo = 0
        if hi < 0:
            return False
    return lo == 0

• lo and hi bracket the range of open-paren counts still achievable given the *s seen so far.
• ( and ) move both bounds together; only * widens the gap between them.
• Clamping lo to 0 (line 14) reflects that a wildcard can always be read as empty instead of ).
• hi < 0 (line 16) means even reading every * as ( cannot cover the ) count — a true failure.
• return lo == 0 (line 17): if 0 unmatched opens is inside the final range, some choice balances the string.

Complexity

We collapse an exponential search into a single linear pass with two integers — O(1) extra space. Instead of committing each * to a value, we carry the whole interval of possibilities at once.

When this pattern shows up

Practice