Valid Parenthesis String
Check a string of '(', ')' and '*' in one greedy pass by tracking the lowest and highest number of open brackets any choice could give.
Problem Understanding
Valid Parenthesis String: s contains '(', ')' and '*'. Each '*' can stand for '(', ')' or an empty string. Return true if some choice makes the brackets balanced.
Examples: "()", "(*)" and "(*))" are all valid; in the last one the * acts as '('.
Attempt 1: Try Every Choice
With no stars, Valid Parentheses needs only a count of open brackets. Each star has three choices, so trying them all costs 3^k. Memoising on (index, open count) brings it to O(n²), but there is a simpler observation.
The Intuition: Track a Range, Not One Count
Instead of one open count, keep the range of counts some choice could produce, [lo, hi]:
'(': everything shifts up,lo + 1,hi + 1.')': everything shifts down,lo − 1,hi − 1.'*': it could close, open or do nothing, so the range widens:lo − 1,hi + 1.
Two rules keep the range honest:
- If
hi < 0, even the most generous choice has too many')': returnfalse. lo = max(lo, 0): a negative count is never a valid choice, so drop it.
At the end, the string is valid exactly when 0 is in the range, i.e. lo == 0. One pass, two integers: a greedy solution.
Interactive Walkthrough
The number line shows every open count still possible after each character. Watch '(' slide the shaded range right, ')' slide it left and '*' stretch it; the string is valid if 0 is shaded at the end.
Dry Run Table
Input: "(*))"
| Char | lo | hi |
|---|---|---|
| ( | 1 | 1 |
| * | 0 | 2 |
| ) | 0 (clamped) | 1 |
| ) | 0 (clamped) | 0 |
lo == 0 at the end: true.
The Solution Template
Greedy range of possible open counts.
Valid Parenthesis String Code
1var checkValidString = function(s) {2 let lo = 0, hi = 0;3 for (const c of s) {4 if (c === '(') { lo++; hi++; }5 else if (c === ')') { lo--; hi--; }6 else { lo--; hi++; }7 if (hi < 0) return false;8 lo = Math.max(lo, 0);9 }10 return lo === 0;11};
Edge Cases & Common Mistakes
- A leading ')':
hidrops to −1 at once; returnfalse. - Clamping before the hi check: check
hi < 0first, then clamplo. - Returning
hi == 0: the string is valid when 0 is reachable, i.e.lo == 0;himay still be positive thanks to stars. - Only stars: any string of
'*'is valid (all empty).
Summary
Track the range [lo, hi] of open-bracket counts any choice of stars could give: '(' shifts it up, ')' down, '*' widens it. Fail as soon as hi < 0, clamp lo at 0, and return lo == 0 at the end. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet