Appearance
4.26.8 — Valid Parenthesis String
LeetCode 678 · Medium
The problem
A string contains (, ) and *. Each * may be treated as (, as ), or as an empty string. Return true if the string can be made valid.
Restating the Problem: You are given a string containing only three types of characters. You want to know if it's possible to balance the parentheses. The catch is the * character, which acts as a wildcard. You get to choose whether each * acts as a left parenthesis, a right parenthesis, or just disappears.
- Constraints to note: The string length is up to 100, which is quite small, but an O(n) solution is what interviewers expect.
- Edge cases: A string of all
*s is valid (they all become empty). A string starting with)immediately fails.
"()" → true
"(*)" → true (* as empty)
"(*))" → true (* as an open bracket)
")(" → falseBrute Force Approach
The naive approach is to use recursion with backtracking. Every time you encounter a *, you branch into three separate recursive calls: one treating it as (, one as ), and one as empty. Since there can be up to n wildcards, this creates 3^n branches. With n = 100, 3^{100} is astronomically large and will result in a Time Limit Exceeded (TLE) error.
The pattern
Without *, a single counter suffices: add one for (, subtract for ), fail if it goes negative, and require zero at the end. That is 4.8.1 Valid Parentheses with one bracket type.
Each * makes the count ambiguous — it could go up, down or stay. Trying all 3^n assignments is hopeless.
An Analogy: Imagine you are playing a board game where ( means "take 1 step forward", ) means "take 1 step back", and * means "roll a special die to either go forward, go back, or stay still". If you want to know all possible spaces you could land on, you don't map out every single timeline. You just track your minimum possible position and your maximum possible position. Since the moves are continuous (no gaps), you can land on any space between that min and max.
The fix:
Do not track the count. Track the range of counts that are still possible.
Two numbers:
lo— the smallest open count possible, assuming every*so far was a closing bracket.hi— the largest, assuming every*was an opening bracket.
Then:
| character | lo | hi |
|---|---|---|
( | +1 | +1 |
) | −1 | −1 |
* | −1 (treat as )) | +1 (treat as () |
Fail when hi < 0. Even the most generous reading has more closers than openers, so no assignment can work.
Clamp lo at 0, never letting it go negative. A negative open count is meaningless — you cannot have −2 unmatched brackets — and it corresponds to an assignment that already failed. Clamping keeps lo describing only the assignments still alive.
Code Walkthrough:
- Initialization: We initialize
lo = 0andhi = 0. - Iteration: We loop through each character in the string.
- Updating Bounds:
- If we see
(, our minimum and maximum open counts both strictly increase. - If we see
), our minimum and maximum both strictly decrease. - If we see
*, our maximum increases (if we choose(), and our minimum decreases (if we choose)).
- If we see
- Checking Failure (
hi < 0): If at any point the maximum possible open brackets drops below zero, it means every possible path has too many closing brackets. We returnFalse. - Clamping (
lo = max(lo, 0)): If the minimum possible open brackets goes negative, we clamp it back to zero. A negative open count means that specific path became invalid, but other paths (represented by values up tohi) are still alive. - Return: At the end, we check if
0is a possible final count by returninglo == 0.
At the end, lo == 0 means some assignment balances, because 0 lies within the reachable range.
Why every count in the range is reachable
This is the part that needs justifying, and it is why two numbers suffice rather than a set.
Flipping a single * from ) to ( changes the count by exactly 2 — but flipping it to empty changes it by 1. Since each * offers three consecutive values, the set of achievable counts at every position is a contiguous range, not a scattering. So the interval [lo, hi] describes it exactly.
That contiguity is what makes the algorithm valid. Without it you would need the whole set.
The solution
python
class Solution:
def checkValidString(self, s: str) -> bool:
lo = hi = 0
for c in s:
if c == '(':
lo += 1
hi += 1
elif c == ')':
lo -= 1
hi -= 1
else: # '*'
lo -= 1 # treat as ')'
hi += 1 # treat as '('
if hi < 0:
return False # too many closers, even at best
lo = max(lo, 0) # a negative count is meaningless
return lo == 0ts
function checkValidString(s: string): boolean {
let lo = 0, hi = 0;
for (const c of s) {
if (c === '(') { lo++; hi++; }
else if (c === ')') { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) return false;
lo = Math.max(lo, 0);
}
return lo === 0;
}The clamp must come after the hi < 0 check, not before, and it applies only to lo. Clamping hi would hide the failure condition entirely.
Return lo == 0, not hi == 0. hi being positive is fine — it just means some assignments left brackets open, and you only need one assignment to balance. lo == 0 says 0 is in the reachable range.
Trace
"(*))"
| c | lo | hi | note |
|---|---|---|---|
( | 1 | 1 | |
* | 0 | 2 | could be ), empty, or ( |
) | 0 (clamped from −1) | 1 | |
) | 0 (clamped from −1) | 0 |
lo == 0 → true ✓. The valid reading is * as (, giving "(())".
And ")(":
| c | lo | hi |
|---|---|---|
) | 0 (clamped) | −1 → return false |
Complexity
O(n) time, O(1) space.
- Time Complexity: O(n). We do a single pass through the string of length n, performing constant-time arithmetic at each step.
- Space Complexity: O(1). We only track two variables (
loandhi), using no extra data structures.
The two other solutions
Two stacks. Keep a stack of indices for ( and one for *. On ), match against an open bracket if possible, otherwise a star. At the end, pair leftover open brackets with leftover stars — and each star must come after the bracket it closes, which is why indices are stored rather than counts. O(n) time and space.
Two passes. Sweep left to right treating every * as ( and check the count never goes negative; then sweep right to left treating every * as ) and check the same. Both passing means valid. Also O(n) time and O(1) space, and it is a nice illustration of check the worst case from each direction.
Write the range version. It is the shortest and it generalises.
Where this goes next
- Minimum Add to Make Parentheses Valid — count the deficits from each side. Much simpler and a good warm-up.
- Minimum Remove to Make Valid Parentheses — two passes marking which brackets to delete.
- Longest Valid Parentheses — a stack of indices with a sentinel, or a DP.
The transferable idea: when a value becomes uncertain, track the interval of possibilities rather than branching. It appears in interval arithmetic, in constraint propagation, and in bounds analysis inside compilers — anywhere the exact value is unknown but its range is cheap to maintain.
What the interviewer will push on
"Why two counters?" Each * makes the open count ambiguous; the range of possible counts is contiguous, so its two endpoints describe it exactly.
"Why clamp lo at 0?" A negative open count corresponds to an already-failed assignment, and keeping it would understate the surviving possibilities.
"Why check hi < 0 and return false?" Even the most generous reading has too many closers.
"Why return lo == 0 rather than hi == 0?" You need one assignment to balance, and 0 being in the range says one does.
"Why is the reachable set contiguous?" Each * offers three consecutive values, so no gaps can form.
One thing to volunteer: name the technique — "instead of branching on each *, I carry the range of possible counts" — and say why the range has no holes. That is the insight; the code is four lines.
Next: 4.27 is the smallest group and the most mechanical — six problems where the only real decision is whether to sort by start or by end.