Minimum Remove to Make Valid Parentheses
On this page
Problem statement
Given a string of lowercase letters and the characters ( and ), remove the fewest brackets so that the brackets in the result are balanced, and return any such result. Letters are never removed.
It extends Valid Parentheses from "is it valid?" to "fix it with the least damage". The key move is to put indices, not characters, on the stack so you know exactly which brackets to drop. Original problem: LeetCode 1249.
Example

Input: "a)b(c)d("
Output: "ab(c)d"
Input: "))(("
Output: ""
Constraints (assumed)
- 1 ≤ length ≤ 100,000.
- Lowercase letters,
(and).
What this question tests
- Reusing the bracket-matching stack, but storing positions.
- Spotting the two kinds of bad bracket: an extra
)and an unclosed(. - Building the output in O(n) without repeated string deletions.
Questions to ask first
- Any minimal answer, or a specific one? (Here: any valid answer with the fewest removals.)
- Only round brackets? (Here: yes. With several types you'd match types too.)
- Can letters be removed? (No.)
- Return the string or just the number of removals? (Here: the string.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.