visual walkthrough
Minimum Remove to Make Valid Parentheses
Tracking indices of unmatched brackets; a frequent Meta question.
The idea
A bracket is "extra" if it can never be matched. A ')' with nothing open before it is extra. Any '(' still unmatched at the end is extra. Everything else stays, so the result is the fewest removals possible.
A stack of indices finds both kinds in one pass; two counter passes find them without a stack.
Complexity
| approach | time | space |
|---|---|---|
| Stack of indices | O(n) | O(n) |
| Two passes with counters | O(n) | O(1) extra |