How many brackets are missing
Count the fewest brackets to add so a row of round brackets matches, noticing that a stack of identical brackets is just a counter. About 12 minutes.
A counter instead of a stack
Reading a row of round brackets from the left, an opening bracket waits for a closer. A closing bracket cancels the nearest waiting opener. When there is only one kind of bracket, all waiting openers look the same, so you do not need a stack to remember which is which. A number saying how many are waiting is enough.
if ch == "(":
open_count += 1
elif open_count > 0:
open_count -= 1An opener. Waiting: 1. Additions: 0.
Two kinds of damage
A closer that finds no waiting opener can never be matched by anything before it. The only fix is to add an opener in front of it, so count one addition.
At the end, every opener still waiting needs a closer added after it. So the answer is the number of additions made on the way, plus the number of openers still waiting.
else:
adds += 1
return adds + open_countHow many brackets must be added to make the text ) ) ( ( match?
- A4
- B2
- C0
Show the answer
4. Both closers need an opener in front, and both openers need a closer after.
Fewest brackets to add
You are given a string s made only of the characters ( and ). In one move you may insert a bracket of either kind at any position. Return the fewest insertions that make s balanced, meaning every opening bracket is matched by a later closing bracket.
s = "())((" → 30 ≤ length of s ≤ 100,000 · s has only ( and )