Minimum Remove to Make Valid Parentheses
Minimum Remove to Make Valid Parentheses is LeetCode 1249 (Medium). The string s holds (, ) and lowercase letters. Remove the fewest parentheses so that what is left is valid: every ( is closed by a later ), and every ) closes an earlier (. Letters always stay.
- Any valid result with the fewest removals is accepted.
- With up to 100,000 characters, the solution has to run in O(n).
- 1 <= s.length <= 10⁵
- s[i] is either '(' , ')', or a lowercase English letter.
Intuition
Scan left to right and pair each ) with the nearest unmatched ( before it. A stack of the positions of unmatched ( does the pairing: push on (, pop on ).
Only two kinds of bracket can never be paired:
- A
)that finds the stack empty: every(before it is taken, and a(after it cannot close it. - A
(still on the stack at the end: no free)came after it.
Removing exactly those is the minimum. Each one must go, because nothing can pair it, and once they are gone every remaining bracket belongs to a matched pair.
Matching brackets is a stack job. For the fewest deletions, find every bracket that can never match instead of stopping at the first error; the positions left on the stack say exactly which ones to delete.
Approach
Before reading on, name the only two situations in which a bracket can never be part of a pair. Then decide what you have to store to know, at the end, which opening brackets were never closed. Aim for O(n).
Two ways to solve it
Push the index of each (, pop on ), and mark the brackets that never pair.
- Direct: the stack says exactly which
(to drop. - One rule: remove what can never be matched.
Left to right, drop each ) with no open ( and count the opens left over. Then right to left, drop that many (.
- No stack: only a counter and the output.
- Two directions: left to right, then right to left.
Both run in O(n). The stack version wins on clarity: it records the exact positions to delete, so there is no second direction to get wrong. The steps, code and live demo follow the stack version, and the counting code comes after the demo.
Keep a stack of open positions
Walk the string with its index. On (, push the index, because this bracket waits for a later partner. Letters are skipped: they never affect whether the string is valid.
Pair or remove each closing bracket
On ), if the stack is not empty, pop it: this ) closes the most recent waiting (. If the stack is empty, mark this ) for removal at once, because nothing before it is free to match it.
Remove the opens left over
When the scan ends, every index still on the stack is a ( that no later ) closed. Mark all of them for removal too, since nothing is left in the string that could close them.
Build the answer once
Join every character that is not marked. Marking first and building once keeps the work O(n), while deleting characters from the string one by one would shift the rest each time and cost O(n²).
Minimum Remove to Make Valid Parentheses solution in Python | C++ | Java
( before this point is already paired. A ( that comes later cannot close a ) before it, so this bracket can never be part of a pair and must be removed.) that comes later, so push its index and keep scanning.( still waiting. This ) closes it, so both are kept and the pair is done.( found a partner. The only removals are the ones marked during the scan.) that comes later, so push its index and keep scanning.) that comes later, so push its index and keep scanning.( still waiting. This ) closes it, so both are kept and the pair is done.( still waiting. This ) closes it, so both are kept and the pair is done.( before this point is already paired. A ( that comes later cannot close a ) before it, so this bracket can never be part of a pair and must be removed.( found a partner. The only removals are the ones marked during the scan.( before this point is already paired. A ( that comes later cannot close a ) before it, so this bracket can never be part of a pair and must be removed.( before this point is already paired. A ( that comes later cannot close a ) before it, so this bracket can never be part of a pair and must be removed.) that comes later, so push its index and keep scanning.) that comes later, so push its index and keep scanning.) after it was free to close it, so it can never be paired and is removed.) after it was free to close it, so it can never be paired and is removed.Two counting passes
The first pass keeps a count of open brackets and skips any ) that arrives when the count is 0. Whatever the count is at the end is the number of ( that never closed, so the second pass walks backwards from the end and skips that many (.
Common pitfalls
Forgetting the opens left on the stack
for i, ch in enumerate(chars):
...
return "".join(chars)for i, ch in enumerate(chars):
...
for i in open_at:
chars[i] = ""
return "".join(chars)An unclosed ( is only known once the scan ends. Without the final loop, "(a" comes back unchanged, and it is not valid; the answer is "a".
Popping without checking the stack
elif ch == ")":
open_at.pop()elif ch == ")":
if open_at:
open_at.pop()
else:
chars[i] = ""A ) with no open partner meets an empty stack. For "a)", Python raises an error and C++ reads past the end of the vector; the answer should be "a".
Dropping the first extra opens instead of the last
for ch in kept:
if ch == "(" and open_count > 0:
open_count -= 1
continue
result.append(ch)for ch in reversed(kept):
if ch == "(" and open_count > 0:
open_count -= 1
continue
result.append(ch)
result.reverse()In the counting version, the ( that never close are always the rightmost ones. For "(()(" two ( are extra: dropping the first two leaves ")(", which is invalid, while dropping the last two leaves "()".
Edge cases
For "))((", both ) are removed during the scan and both ( at the end, so the answer is the empty string, which counts as valid.
Several results can tie. For "lee(t(c)o)de)", "lee(t(co)de)" and "lee(t(c)ode)" are also accepted; the stack method happens to return "lee(t(c)o)de".
Complexity
(, and the result is up to n characters.Parentheses problems that look alike
Four LeetCode problems share the same strings but ask for different things:
| Problem | Asks for | Method |
|---|---|---|
| 20 Valid Parentheses | is the string already valid? | stack, stop at the first mismatch |
| 921 Minimum Add to Make Parentheses Valid | how many brackets to insert | count unmatched ) and leftover ( |
| 1249 Minimum Remove (this page) | one valid string with the fewest removals | stack of positions, delete the unmatched |
| 301 Remove Invalid Parentheses | every distinct valid string with the fewest removals | BFS or backtracking over removals (Hard) |