Minimum Remove to Make Valid Parentheses
Medium · Stack & Strings · String · Stack
Problem
You are given a string s of lowercase letters and the characters ( and ). Remove as few parentheses as possible, from any positions, so that the rest is a valid parentheses string, and return the result. Letters are never removed.
A string is valid when every ) closes an earlier unmatched ( and every ( is closed by a later ); letters may appear anywhere. The empty string and strings of letters only are valid.
When several results need the same smallest number of removals, any of them is accepted.
Examples
Input: s = "(a))b" Output: "(a)b"
The second ) has nothing left to close. Removing either ) gives the same string, (a)b.
Input: s = "a(b(c)d" Output: "ab(c)d"
One ( is never closed. Removing the first gives ab(c)d; removing the second gives a(bc)d, which is also accepted.
Input: s = "))(("
Output: ""No ) has an earlier ( to close, so all four characters go.
Constraints
- 1 <= s.length <= 10^5
- s[i] is '(', ')' or a lowercase English letter
Approaches
- Remove one unmatched parenthesis at a time — time O(n²), space O(n)
Follow-up
Listing every distinct valid string with the minimum number of removals is much harder: the number of results can grow quickly, and the usual approach is a breadth-first or backtracking search that removes one parenthesis at a time and skips duplicates.
Related problems
Start free on Cariara · Coding problems · System design studio
