Valid Parenthesis String

Carry a range of open counts, never commit a '*'

time O(n)space O(1)

Trying each '*' as '(' , ')' or nothing explodes into 3^k strings, and a stack cannot help because it would have to commit to one meaning before knowing the future. The greedy escape is to stop tracking a single open count and track the RANGE of open counts that are still reachable: lo is the fewest '(' that could be open, hi the most. A '(' lifts both ends, a ')' drops both, a '*' pushes lo down and hi up at the same time, keeping every reading alive in two numbers. Two rules finish it. If hi ever goes below 0, even the most generous reading has an unmatchable ')' and nothing later can repair it, so reject immediately. And lo floors at 0 rather than going negative — the readings that ran out of brackets simply die off while the others continue. At the end, lo = 0 means some surviving reading closed everything, which is exactly the answer.

Details

Animated on: s = "(*))*(*)" — each '*' may be '(', ')' or empty. Is there any reading that makes the string balanced?

Problem:Valid Parenthesis StringMedium

Carry a range of open counts, never commit a '*'

step 1 / 10

(

[0]

[1]

)

[2]

)

[3]

[4]

(

[5]

[6]

)

[7]

Never guess what a '*' means — carry every reading at once. lo is the FEWEST '(' that could still be open, hi the MOST. Both start at 0, and the string is valid if some reading ends with nothing open.

Pseudocode

1FUNCTION checkValidString(s)
2  lo <- 0
3  hi <- 0
4  FOR i <- 0 TO LENGTH(s) - 1
5    IF s[i] = '('
6      lo <- lo + 1
7    ELSE
8      lo <- MAX(lo - 1, 0)
9    IF s[i] = ')'
10      hi <- hi - 1
11    ELSE
12      hi <- hi + 1
13    IF hi < 0
14      RETURN false
15  RETURN lo = 0

← / → step · space play · Home restart

Every step in words

Show all 10 steps

Never guess what a '*' means — carry every reading at once. lo is the FEWEST '(' that could still be open, hi the MOST. Both start at 0, and the string is valid if some reading ends with nothing open.
s[0] = '('. '(' is not ambiguous — it opens a bracket in every reading at once, so both ends of the range rise together. Open count is now exactly 1.
s[1] = '*'. '*' is the fork: read as ')' or as nothing it pushes the count DOWN to 0, read as '(' it pushes it UP to 2. Rather than pick one, the range WIDENS to 0..2 and both futures stay alive.
s[2] = ')'. ')' closes a bracket in every reading, so both ends fall together to anywhere from 0 to 1. lo wanted to be -1: the readings holding the fewest brackets have nothing left to close, so those readings are dead — but readings sitting at 0 survive, which is why lo floors at 0 instead of going negative.
s[3] = ')'. ')' closes a bracket in every reading, so both ends fall together to exactly 0. lo would be -1 again, and floors at 0 again. hi is 0 now, the razor edge: even the most generous reading has everything closed, so one more ')' would drop hi below 0 and no reading could absorb it.
s[4] = '*'. '*' still forks, but lo is already resting on the floor: read as '(' it lifts hi to 1, while read as ')' or as nothing it has no room left to push lo below 0. Range 0..1.
s[5] = '('. '(' is not ambiguous — it opens a bracket in every reading at once, so both ends of the range rise together. Open count is now anywhere from 1 to 2.
s[6] = '*'. '*' is the fork: read as ')' or as nothing it pushes the count DOWN to 0, read as '(' it pushes it UP to 3. Rather than pick one, the range WIDENS to 0..3 and both futures stay alive.
s[7] = ')'. ')' closes a bracket in every reading, so both ends fall together to anywhere from 0 to 2. lo would be -1 again, and floors at 0 again.
hi never went below 0, so no prefix ever had an unmatchable ')'. At the end lo = 0, meaning some reading of the '*'s finishes with nothing left open — that reading is a balanced string, so this is valid.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Valid Parenthesis String in the editor All Greedy problems Back to roadmap