Valid Parenthesis String
Understanding the Problem
This is the classic valid parentheses problem with one addition: the wildcard *. Without *, the answer comes from a single counter: increment on (, decrement on ), and check that it never goes negative and ends at zero.
The * complicates this because at each * position there are three choices: treat it as (, as ), or as nothing. Trying all combinations explodes exponentially. The real question is whether there exists some assignment of wildcards that makes the string valid, without enumerating every assignment.
We don't need the exact assignment. We only need to know whether the range of possible open-parenthesis counts at the end includes zero. By tracking the minimum and maximum possible count of unmatched ( at each position, validity falls out of a single pass.
Key Constraints:
1 <= s.length <= 100: n is small enough that an O(n^2) DP passes, and an O(n) greedy is comfortable. The small bound is what lets the brute force and DP approaches below run in time at all.s[i]is'(',')'or'*': only three character types, so there are no other cases to handle.
Approach 1: Brute Force (Recursion)
Intuition
Try every possibility. At each *, branch into three recursive calls that treat it as (, as ), or as the empty string. For ( and ), adjust the open-parenthesis counter as usual.
If any branch reaches a valid state (counter equals zero at the end and never went negative), the string is valid. This is an exhaustive search over all wildcard assignments.
Algorithm
- Define a recursive function that takes the current index and the count of unmatched open parentheses.
- If the count ever goes negative, return false (too many closing parens).
- If we reach the end of the string, return true only if the count is exactly zero.
- For
(, recurse with count + 1. - For
), recurse with count - 1. - For
*, try all three: recurse with count + 1, count - 1, and count unchanged. Return true if any branch returns true.
Visualization and Code
Loading animation...
- Time Complexity: O(3^n). At each
*character, we branch into 3 recursive calls. In the worst case where every character is*, this gives us 3^n total calls. - Space Complexity: O(n). The recursion depth is at most n, since we advance the index by 1 at each level.
The state at any point is fully determined by the current index and the open-parenthesis count, yet this recursion recomputes the same (index, openCount) states many times. Caching those results removes the repeated work.
Approach 2: Dynamic Programming (Memoization)
Intuition
The recursion from Approach 1 has overlapping subproblems. The state is (index, openCount), and since index ranges from 0 to n and openCount ranges from 0 to n, there are at most O(n^2) distinct states. Caching their results removes the exponential blowup.
Each state answers one question: starting at position index with openCount unmatched open parens, can the rest of the string be completed validly? Once that question is answered, every later call with the same state reads the stored answer instead of recursing again.
Algorithm
- Create a memoization table (hash map or 2D array) indexed by (index, openCount).
- Use the same recursive logic as Approach 1.
- Before computing, check if the state (index, openCount) is already in the memo. If so, return the cached result.
- After computing, store the result in the memo before returning.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). There are O(n) possible indices and O(n) possible open-count values (0 to n), giving O(n^2) unique states. Each state is computed once with O(1) work.
- Space Complexity: O(n^2). The memoization table stores O(n^2) states. The recursion stack adds O(n) depth, but this is dominated by the table.
The next approach replaces the table entirely. Instead of tracking every reachable open count individually, it tracks only the range of reachable open counts, which collapses the state down to two variables.
Approach 3: Greedy (Min-Max Range)
Intuition
This problem is solvable in O(n) time and O(1) space by tracking only two numbers instead of the full set of reachable open counts: the minimum and maximum possible count of unmatched open parentheses.
Without wildcards, there is exactly one open count at each position. With wildcards, there is a range, and that range stays contiguous because every reachable count between the minimum and maximum is also reachable (any single * you flipped from ( to ) shifts the total by exactly 1). So we maintain low (minimum possible open count) and high (maximum possible open count):
(increases both by 1)decreases both by 1*decreaseslowby 1 and increaseshighby 1
Two checks guard the range. If high drops below 0, even treating every * as ( leaves an unmatched ), so return false. And low can never represent fewer than zero unmatched opens, so we clamp it at 0. At the end, if low is 0, zero is within the range and a valid assignment exists.
Clamping low at 0 is safe because a prefix that would push the minimum below 0 can always assign one more * (or () as a non-closing character to keep the count at 0, so 0 stays a reachable open count. The validity test is whether 0 lies in the final range [low, high]. The high < 0 early exit already rules out the case where 0 is above the range, and low is clamped at 0, so 0 is in range exactly when low == 0.
Algorithm
- Initialize
low = 0andhigh = 0. - For each character in the string:
- If
(: increment bothlowandhigh. - If
): decrement bothlowandhigh. - If
*: decrementlowby 1, incrementhighby 1. - If
high < 0: return false (too many)even with all*as(). - Clamp
lowto at least 0 (can't have negative unmatched(). - Return
low == 0.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We iterate through the string exactly once, doing O(1) work per character.
- Space Complexity: O(1). We only use two integer variables regardless of input size.