Remove Invalid Parentheses
Hard · Backtracking · String · Backtracking · Breadth-First Search
Problem
You are given a string s of lowercase letters and parentheses. Remove the minimum number of parentheses that makes the string valid: every ( is closed by a later ), and no prefix has more ) than (.
Return all distinct valid strings that can be made with that minimum number of removals, in any order. Letters are never removed.
Examples
Input: s = "(x))("
Output: ["(x)"]One extra ) and the trailing ( must go, and every way of removing them leaves (x).
Input: s = "(()()" Output: ["(())","()()"]
Dropping one of the two unmatched ( characters gives two different valid strings.
Input: s = "a)b(c)" Output: ["ab(c)"]
Only the first ) is unmatched.
Constraints
- 1 <= len(s) <= 25
- s consists of lowercase English letters and the characters ( and )
- s contains at most 20 parentheses
Approaches
- Breadth-first, one removal per level — time O(2^p · n), space O(2^p · n)
Follow-up
The search can avoid producing duplicates instead of filtering them: inside a run of equal parentheses, removing any one of them gives the same string, so only allow removing the first of the run at each level. Then every result is generated once and the set is not needed.
Related problems
Start free on Cariara · Coding problems · System design studio
