Valid Parenthesis String Solution

Problem

Given a string containing only (, ), and *, determine whether it can be made into a valid parenthesis sequence. Every ( must be closed by a ), every ) must be preceded by a matching (, and each * can act as a (, a ), or an empty string — you decide which role each * plays.

Input: s = "(*)"
Output: true
Explanation: Replace * with an empty string, leaving "()", which is valid.

Counter-example: "(*(((" returns false — even using * as ) still leaves four unmatched ( that nothing can close.

Intuition

The brute-force reads this as a search problem: at every *, branch into three choices and check if any path produces a balanced string. That works but explodes to O(3ⁿ). The greedy insight is that you don't need to commit to one choice. Instead, track the range of possible unmatched-open counts across all valid interpretations simultaneously. If zero is reachable at the end of the string, the answer is true.

Approach 1 — Backtracking

Recursively try all three roles for each *, pruning as soon as the open count goes negative.

At index 0, start with open count 0.
For (, recurse with open count incremented by 1.
For ), recurse with open count decremented; prune if it goes below 0.
For *, branch into three recursive calls: treat as (, as ), or as empty.
Return true if the open count reaches exactly 0 at the end of the string.

1def checkValidString(s: str) -> bool:
2    def backtrack(index: int, open_count: int) -> bool:
3        if open_count < 0:  # impossible to recover — prune this branch
4            return False
5        if index == len(s):
6            return open_count == 0
7        char = s[index]
8        if char == '(':
9            return backtrack(index + 1, open_count + 1)
10        elif char == ')':
11            return backtrack(index + 1, open_count - 1)
12        else:  # '*' — try each possible role
13            return (backtrack(index + 1, open_count + 1) or  # treat as '('
14                    backtrack(index + 1, open_count - 1) or  # treat as ')'
15                    backtrack(index + 1, open_count))         # treat as empty
16    return backtrack(0, 0)

Time: O(3ⁿ) — each * triples the search space, so worst case is three branches at every character.
Space: O(n) — recursion depth equals the length of the string.

Approach 2 — Greedy Range Tracking

Instead of committing to one interpretation of each *, maintain a running window [min_open, max_open] representing the minimum and maximum number of unmatched ( that are possible across all valid interpretations.

Initialize min_open = 0 and max_open = 0.
For (: both bounds increase by 1 — one more unmatched open in every interpretation.
For ): both bounds decrease by 1 — one open gets closed in every interpretation.
For *: max_open increases by 1 (treating * as () and min_open decreases by 1 (treating * as ) or empty) — the possible range widens.
If max_open drops below 0, even the most optimistic interpretation is unbalanced — return false immediately.
Clamp min_open at 0 — a negative value would mean we opened more ) than (, which is impossible; the minimum achievable open count is 0.
After scanning the whole string, return true if min_open == 0 — zero unmatched opens must be achievable in at least one interpretation.

1def checkValidString(s: str) -> bool:
2    min_open = 0  # fewest possible unmatched '(' across all interpretations
3    max_open = 0  # most possible unmatched '(' across all interpretations
4    for char in s:
5        if char == '(':
6            min_open += 1
7            max_open += 1
8        elif char == ')':
9            min_open -= 1
10            max_open -= 1
11        else:  # '*' widens the achievable range
12            min_open -= 1  # best case: '*' is ')' or empty, reducing opens
13            max_open += 1  # best case: '*' is '(', increasing opens
14        if max_open < 0:  # no interpretation survives — unrecoverable
15            return False
16        min_open = max(min_open, 0)  # negative open count is physically impossible
17    return min_open == 0  # zero unmatched opens must be achievable

Time: O(n) — one pass through the string with constant work per character.
Space: O(1) — only two integer variables regardless of input length.

Complexity Summary

Approach	Time	Space	When to use
Backtracking	O(3ⁿ)	O(n)	Only for understanding all possibilities; impractical for n > 20
Greedy Range	O(n)	O(1)	Always — optimal for any input size

Common Mistakes

Checking min_open < 0 instead of max_open < 0 for early exit — the string can still be valid when only the minimum drops below 0 (some interpretations of * may keep it non-negative). You only fail when even the most optimistic interpretation goes negative, i.e., max_open < 0.
Forgetting to clamp min_open at 0 — after processing a * as ), min_open can become -1. Leaving it negative infects all subsequent calculations, making the final check incorrect. A negative open count simply means "we could have closed everything and more," so clamp it to 0.
Checking max_open == 0 at the end instead of min_open == 0 — max_open being 0 means the greediest use of every * as ( still balanced out, which is a stronger (and wrong) condition. You need the most conservative scenario to reach zero.
Using a single running count instead of a range — a single count forces you to pick one role for * upfront. The greedy approach works precisely because it defers the choice by tracking what's possible, not what's committed.
Missing the implicit constraint that min_open must end at 0, not just ≤ 0 — it's clamped at 0 throughout, so at the end it's either 0 (some valid interpretation exists) or positive (all interpretations leave unmatched opens).

Valid Parenthesis String — Solution