Pattern visualizer
Valid Parenthesis String
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. Animated on: s = "(*))*(*)" — each '*' may be '(', ')' or empty. Is there any reading that makes the string balanced?.
Carry a range of open counts, never commit a '*'
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.
1FUNCTION checkValidString(s)2 lo <- 03 hi <- 04 FOR i <- 0 TO LENGTH(s) - 15 IF s[i] = '('6 lo <- lo + 17 ELSE8 lo <- MAX(lo - 1, 0)9 IF s[i] = ')'10 hi <- hi - 111 ELSE12 hi <- hi + 113 IF hi < 014 RETURN false15 RETURN lo = 0
← / → step · space play · Home restart