#678
Valid Parenthesis String
Medium Range of open counts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A string has '(', ')' and '*', where '*' can be '(', ')' or empty. Decide whether it can be a valid parentheses string.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: with '*' as '(', ')' or nothing, can the string be valid?
Why this works: track the possible range of open brackets [lo, hi]; '*' widens it.
Example: "(*))"
'(' → [1,1], '*' → [0,2], ')' → [0,1], ')' → [0,0]lo reaches 0 → valid
✦Hints open one at a time
Track the possible range [lo, hi] of open brackets.
'(' raises both, ')' lowers both, '*' lowers lo and raises hi.
If hi drops below 0, fail. Keep lo at least 0.
↗Approach
One pass maintaining lo and hi. At the end, valid if lo == 0 (some choice closes everything).
</>Solution (Java)
class Solution {
public boolean checkValidString(String s) {
int lo = 0, hi = 0; // min and max possible open count
for (char c : s.toCharArray()) {
if (c == '(') { lo++; hi++; }
else if (c == ')') { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) return false; // too many ')' even at best
lo = Math.max(lo, 0);
}
return lo == 0;
}
}!Common mistake
Treating every '*' as one fixed choice — you need to keep all options open.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Greedy
🎬 Episodes 69–73: video coming soon