DSA problem
Remove Invalid Parentheses
Given a string s that contains parentheses and lowercase letters, remove the minimum number of invalid parentheses to make the input string valid. Return all the possible results in any order. A string is valid if every ( has a matching ) later and the closing parentheses never outnumber the opening ones at any prefix.
The key insight is to first compute exactly how many ( and how many ) characters must be removed. Scan once: maintain counters extra_open and extra_close. For each character, if it is ( increment extra_open; if it is ) then either match a pending open (extra_open--) or, if none is pending, increment extra_close. The pair (extra_open, extra_close) is the minimum removals.
Now perform a DFS over the string: at each character, you have two choices — keep it or skip it. Two pruning rules accelerate things: stop early if no ( removals are needed (extra_open == 0) and the current character is ( we are about to skip; stop early similarly for ). Skip a removal only when its budget is positive. Also, to avoid generating duplicate results, do not "skip" two consecutive identical parentheses at the same level — only consider skipping the first of a run.
When you reach the end of the string with both budgets exhausted, validate that the kept string has no mismatched parentheses (or maintain a running open/close balance during the DFS to enforce this on the fly) and add it to the results. Using a set during collection also defends against any leftover duplicates from corner cases. Total time is exponential in the worst case but tightly bounded by the minimum-removal property.
Examples
s = "()())"["(())","()()"]s = "(a)())()"["(a())()","(a)()()"]s = ")("[""]Constraints
- 1 <= s.length <= 25
- s consists of lowercase English letters and parentheses '(' and ')'.
- There will be at most 20 parentheses in s.
- The output may be returned in any order.
- No duplicate result strings should appear in the output.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.