840. Removing the Fewest Brackets
A line contains round brackets and lowercase letters. Delete the SMALLEST possible number of
brackets so that what remains is balanced: every ( has a later matching ) and every ) has an
earlier matching (. Letters are never deleted and never affect matching.
To make the answer unique, the brackets you delete are exactly the ones with no partner:
* a ) is deleted when there is no unmatched ( anywhere before it
* a ( is deleted when no ) after it is left over to pair with it
Print what remains, keeping the original order. Print the word empty if nothing remains.
lee(t(c)o)de) -> lee(t(c)o)de
a)b(c)d -> ab(c)d
))(( -> empty
In the first line the final ) has nothing left to pair with, so it goes. In the second the
leading ) has no opener before it at all.
## Why a single counter is not enough
Counting depth with one integer tells you a string is unbalanced but not WHICH bracket to blame.
Scanning left to right, an unmatched ) is identified the moment it appears (the depth would go
negative), but an unmatched ( cannot be identified until the whole line has been read, since a
partner may still arrive.
So the two kinds of offender are found at different times, and that is what the stack is for.
## The stack, and what it holds
Push the POSITION of every (. On a ), if the stack is non-empty, pop: those two are partners
and both survive. If the stack is empty, that ) is an orphan and is marked for deletion
immediately.
When the line ends, the stack holds the positions of exactly the openers that never found a partner. Mark those for deletion too.
This is not a monotonic stack in the comparison sense, but it is the same discipline: the stack holds the items still waiting for something from the future, the arriving item settles the most recent one, and what survives at the end is a specific, meaningful set rather than leftovers.
## Why this deletes as few as possible
Every deleted bracket is genuinely unpairable. The orphan closers have no opener available before them at all, so any balanced subsequence must exclude them. The leftover openers have no closer available after them, likewise. So each deletion is forced, and the count is a lower bound that this method achieves.
## What is easy to get wrong
Pop the stack on a ) only when it is NOT empty. Popping an empty stack is the crash, and
skipping the orphan mark is the silent wrong answer: a)b(c)d would come back unchanged.
Marking by position and then rebuilding in one final pass keeps the letters in place. Rebuilding from the stack alone loses them.
## Related problems
Problem 152 only asks whether the line is already balanced, and problem 171 asks for the longest already-balanced stretch rather than repairing the line.
## Cost
Time O(n), one scan plus one rebuild. Space O(n).
Constraints - `1 ≤ |s| ≤ 200000` - `s` contains only `(`, `)` and lowercase letters
Input
One line containing the string, made of (, ) and lowercase letters.
Output
Print the repaired string on one line, in the original order with the unmatched brackets removed. If nothing remains, print the single word empty. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.