524. Fewest Insertions to Balance
A string of round brackets is BALANCED when every ( has a matching ) after it and
every ) has a matching ( before it. You may insert brackets anywhere. Print the fewest
insertions needed to make the string balanced.
( -> 1 insert ) after it
)( -> 2 one at each end
(() -> 1
## Why no table is needed
A single left-to-right pass with two counters:
``` open = 0 how many ( are currently unmatched need = 0 how many ( must be INSERTED before this point
for each character: if it is (: open += 1 else: if open > 0: open -= 1 match it against a pending ( else: need += 1 nothing to match, so insert a (
answer = need + open ```
## Why the counters are enough
The key observation is that a ) with no pending ( can ALWAYS be fixed by inserting one
( immediately before it, and that insertion never makes anything else worse: it adds an
opener that is consumed at once.
Similarly, every ( still open at the end needs exactly one ) appended, and appending at
the very end can never unbalance anything before it.
So the two defects are independent and each costs exactly one insertion. The total is their sum, and there is nothing to optimise over.
That independence is what removes the DP. Compare it with problem 510, where an insertion's usefulness depends on the whole rest of the string and a table is unavoidable.
## Why matching greedily is safe
When a ) arrives and some ( is pending, matching them is never worse than leaving the
( open, because an open ( will eventually cost an insertion and a matched one costs
nothing.
The counter open need only be a COUNT rather than a stack, since round brackets are all
interchangeable. With several bracket types it would have to be a stack, and that is the
difference between this problem and #152.
## Boundaries
( and ) each answer 1, the smallest cases in each direction.
)( answers 2, which is the case where the string has equal counts of each bracket and is
still not balanced. A solution that answers abs(count of ( minus count of )) gives 0 here
and is the most common wrong approach.
()())( answers 2 and is the longer version of the same trap: three of each bracket, so
the count difference is 0, and two insertions are genuinely needed.
## Cost
Time O(n). Space O(1).
## Where this appears again
The running-counter treatment of bracket strings gives the validity check, the longest valid substring, the minimum removals to balance, and the "each opener needs two closers" variant. The question to ask each time is whether the defects are independent, because that is what decides between two counters and a table.
Constraints - `1 ≤ length of the string ≤ 200000` - the string contains only `(` and `)`
Input
The first line contains a string of the characters ( and ).
Output
Print the fewest insertions needed to make the string balanced.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.