Greedy
Carrying a range instead of a value
When a choice is genuinely undecidable now, track every outcome it could lead to at once.
Key idea
A symbol that could be either thing
Validate a bracket string where some positions are wildcards that may act as an opener, a closer, or nothing at all.
The search version tries all three at each wildcard and is exponential. The table version is quadratic. There is a linear answer, and it comes from a genuinely different idea rather than from tightening either of those.
Why it works
Track the smallest and largest possible open count
You cannot decide what a wildcard is when you meet it. So do not. Carry the range of open-bracket counts that are still possible, as two numbers: the lowest and the highest.
An opener raises both. A closer lowers both. A wildcard lowers the low and raises the high, since it could be either.
The string is valid if the range never becomes entirely negative along the way, and if zero is inside the range at the end.
The range is easiest to believe when you watch it widen and narrow. Below it is printed after each character, with no decisions made anywhere.
Gotcha
The low is clamped at zero, and that is not cosmetic
A negative low would mean more closers than openers, which is not a real state; the wildcards that caused it can simply be treated as nothing instead. Clamping records that those interpretations are abandoned rather than tracked.
Without the clamp, a string of many wildcards drives the low arbitrarily negative and the final check for zero fails on valid input. It is one line and it is doing real work.
Why it works
Why a negative high is fatal
The high is the most open brackets that could possibly be outstanding. If even that is negative, every interpretation has seen more closers than openers, and no later character can undo it.
So that is the only place the function can fail early. The low reaching zero is recoverable; the high going negative is not.
Tip
The final check is on the low, not the high
At the end, zero must be achievable. Because the low is clamped and the high only grows on wildcards, zero is in the range exactly when the low is zero.
Checking the high instead would accept strings with unmatched openers. Being able to say why the low is the right one to check is what separates understanding this from having copied it.
Key idea
The general technique
When a decision cannot be made locally and its outcomes form a contiguous range, carry the range. Two numbers replace an exponential search whenever every value between the extremes is also achievable.
That achievability condition matters. If the reachable states were scattered rather than contiguous, two bounds would not describe them and this would be wrong. Here every intermediate count is reachable by choosing how many wildcards to treat as nothing.
Cost
Cost
One pass, two variables, so O(n) time and O(1) space, against a quadratic table and an exponential search.
This is the largest gap in the unit between the obvious solution and the intended one, and it comes entirely from the decision to represent uncertainty rather than resolve it.
Predict the output: is every value in the range really achievable?
After two wildcards, the possible counts of open brackets are listed by working out every interpretation. Type the two lines it prints.
Valid Parenthesis String
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.