1224. The Smallest Balanced String the Pattern Could Be

A pattern is made of (, ) and ?. Replace every ? with ( or ) so that the result is balanced, meaning every closing bracket matches an earlier opening one and none is left over. Report the lexicographically smallest balanced result, or none if there is none. ( sorts before ).

(?))?) -> (())() ?? -> () )? -> none

## What most people try first

Try both characters at every ?, over all 2^q combinations, and keep the smallest balanced string. With 400 wildcards that is beyond counting. The point is that a prefix can already be hopeless and the enumeration does not notice: once the running balance goes negative, no suffix repairs it, and every completion of that prefix is still generated.

## The two prunes

Track the running balance, opening brackets minus closing ones.

• It must never go below zero. A closing bracket with nothing open can never
• be matched by anything later, since later characters are to its right.
• It must never exceed the number of characters still to come. Each of those
• closes at most one open bracket, so a balance of b with fewer than b
• characters left can never reach zero.

Both are sound because the balance moves by exactly one per character, so these are statements about what the remaining characters CAN do rather than guesses about what they will do. Together they are not merely prunes: a prefix that satisfies both always extends to a balanced string, so the search never backtracks at all and the whole thing runs in one pass.

## Why the first complete string is the smallest

The positions are filled left to right and the options at a ? are tried ( then ), which is increasing order. Any other balanced completion differs from the first one found at some position where it took ) while the first took (, and ( sorts before ), so the first one found is smaller. Nothing is compared and nothing is stored.

## Why the reference does not recurse

The search is one decision per position and the input can be 1200 characters long, so a recursion goes 1200 frames deep. Python's default recursion limit is 1000, and raising it does not raise the C stack that CPython actually uses, so a recursive reference crashes here. It is not only Python: a frame holding a few locals is tens of bytes, and at tens of thousands of positions the default thread stack in Java and the main stack in C run out too.

So the reference carries the stack itself. The only thing a recursive frame holds that a loop would lose is WHICH OPTION the frame was about to try next, so that is what the explicit stack stores:

``` nxt[i] = index of the next option to try at position i

i = 0; nxt[0] = 0 while i >= 0: if i == n: a complete string if accepted: answer it and stop i = i - 1 otherwise go back continue if nxt[i] has run past the options at i: i = i - 1 this position is exhausted, go back continue take option nxt[i] and increment nxt[i] <- this is the resume point if the option is refused: continue stay at i, try the next one record it; nxt[i+1] = 0; i = i + 1 descend ```

Three details make or break it. nxt[i] is incremented BEFORE the descent, so coming back to position i continues from the next option rather than repeating the one that just failed, which would loop forever. nxt[i+1] is reset to 0 on every descent, not once at the start, because position i+1 may be entered many times and each entry must start from its first option. And going back is i = i - 1 with no undo of out[i], because out[i] is overwritten before it is ever read again; the carried state lives in stv[i], indexed by position, so it unwinds for free.

## The settled boundaries

An odd-length pattern can never balance, so the answer is none; that is tested at length 1 and at length 15. A pattern of all wildcards gives every opening bracket first, ((( ... ))), because ( is the smaller character and the balance bound permits it. A pattern starting with a fixed ) is immediately hopeless.

## Cost

O(n) after the two prunes, since no step is ever undone.

Constraints - `1 ≤ length of the pattern ≤ 1200` - every character is `(`, `)` or `?` - the length can exceed a 1000-frame recursion, so the reference uses an explicit stack