Remove Invalid Parentheses
Understanding the Problem
We have a string with letters and parentheses, and some of those parentheses are invalid. The task is to find all the ways to remove the minimum number of parentheses so that every remaining parenthesis is properly matched, and return all distinct valid results.
Two requirements make this harder than producing a single valid string. We need every valid result, not just one, and the removal count must be the minimum. If removing 2 parentheses can make the string valid, removing 3 is not allowed even if that also produces a valid string.
A string is valid when scanning left to right keeps a running balance (plus one for (, minus one for )) that never drops below zero and ends at exactly zero. To make a string valid with the fewest removals, we first determine how many parentheses are unmatched: every ) that appears with no unclosed ( before it, and every ( left open at the end. The number of unmatched parentheses is exactly the minimum number of removals.
Key Constraints
1 <= s.length <= 25. The string is short, so exponential approaches that explore subsets of removals are feasible.- At most 20 parentheses. Each parenthesis is either kept or removed, so the search space is bounded by 2^20, about a million states. That makes brute-force search practical while still rewarding pruning.
Approach 1: BFS (Level-by-Level Removal)
Intuition
Start with the original string. If it is already valid, return it. Otherwise, generate every string that results from removing one parenthesis, and check whether any of those are valid. If some are, collect them and stop. If none are, repeat: from each of those strings, remove one more parenthesis, and check again.
This is breadth-first search over strings. Each level removes one additional parenthesis. The first level that contains valid strings gives the minimum number of removals, because BFS reaches every string with k removals before any string with k+1 removals. Once a valid string appears at some level, no string at a deeper level can be an answer, so the search stops.
One string can be produced by more than one sequence of removals. For input "())", removing the ) at index 1 and removing the ) at index 2 both produce "()". A visited set tracks which strings have already been generated so each is processed once.
Algorithm
- Add the original string to a queue and a visited set.
- While the queue is not empty, process all strings at the current level.
- For each string, check if it's valid. If valid, add it to the result list.
- If we found any valid strings at this level, return the result (minimum removals guaranteed).
- Otherwise, for each string, generate all possible strings by removing one parenthesis at each position. Add unseen strings to the queue and visited set.
Example Walkthrough
Code
- Time Complexity: O(n * 2^n). In the worst case, we generate all possible subsets by removing characters. For each string, we do an O(n) validity check.
- Space Complexity: O(2^n). The visited set and queue can hold up to 2^n unique strings in the worst case.
BFS explores every string at each removal level, including many that can never lead to a valid result. The next approach computes the exact number of ( and ) to remove first, then explores only the choices that respect that budget.
Approach 2: Backtracking with a Removal Budget
Intuition
BFS does not know how many removals are needed, so it regenerates entire levels. We can fix the removal count before searching. Scan the string once with a running balance: every ( is a candidate open, every ) matches the most recent unmatched ( if one exists, otherwise it is unmatched. After the scan, openToRemove is the number of ( left unmatched and closeToRemove is the number of ) that had no ( to match. Those two counts are the exact budget, and any valid answer removes precisely that many of each.
With the budget known, walk the string left to right. At each parenthesis there are two choices: keep it or remove it. Removing a ( spends one unit of openToRemove; removing a ) spends one unit of closeToRemove. Keeping a character also tracks a running balance so prefixes that can never be valid are cut off.
Two checks keep the search inside valid territory. A ) is only kept when the current balance is positive, since keeping it otherwise produces a prefix with more ) than (. A branch is abandoned as soon as a removal counter would go negative, because that would exceed the budget. When the walk reaches the end with balance back to zero and both counters spent, the built string is a valid answer. A set collects results so the same string produced by different removal choices is stored once.
Algorithm
- Scan the string once to compute
openToRemove(unmatched() andcloseToRemove(unmatched)). - Backtrack from index 0 with an empty path and balance 0.
- For
(: optionally remove it ifopenToRemove > 0, otherwise keep it and increase balance. - For
): optionally remove it ifcloseToRemove > 0, and keep it only when balance is positive, decreasing balance. - For a letter: always keep it.
- At the end of the string, if balance is 0 and both counters are 0, add the path to the result set.
Example Walkthrough
Code
- Time Complexity: O(2^n). Each parenthesis branches into keep or remove. With at most 20 parentheses the bound is 2^20 paths, and the budget and balance checks cut most branches before reaching the end.
- Space Complexity: O(n). The recursion depth is at most n, and the path holds at most n characters.
The budget keeps the search inside valid removal counts, but a set is still needed at the end because different keep/remove choices can build the same string. The next approach removes parentheses position by position and skips over runs of identical characters, so it never generates a duplicate and needs no set at all.
Approach 3: Iterative Removal with Duplicate Skipping
Intuition
The previous approaches rely on a set to drop duplicate strings. Duplicates come from one source: removing any one parenthesis inside a run of identical parentheses produces the same string. Removing the first or the second ) from "))" both leave ")". If, within a run of identical parentheses, removals are restricted to the first one in the run, every distinct result is generated once and no set is needed.
The approach scans for the first position where there are too many ) (the running balance drops below zero). Every excess ) must be fixed by removing one ) at or before that position. For each candidate removal that starts a run of ), recurse on the shortened string. The scan resumes from where it left off rather than restarting, which avoids re-removing earlier parentheses and keeps the work linear per call.
That handles strings with too many ). Too many ( is the mirror image: reverse the string, swap the roles of ( and ), and run the same scan. The second pass catches every unmatched (. Reversing a second time at the end restores the original order. Because each pass only ever removes the closing character of the current orientation, and only at the start of a run, no duplicate is ever produced.
The lastJ parameter remembers where the last removal happened so candidate removals in the next call do not back up before it. Without it, removing position 2 in one branch and position 4 in another could both lead to removing the remaining one and produce the same string twice.
Algorithm
- Scan the string from
lastI, tracking balance. When balance drops below zero at indexi, there is one too many)up to that point. - For each
jfromlastJtoiwheres[j]is)and it is the first)in its run (s[j-1]is not)), removes[j]and recurse with the scan resuming atiand removals resuming atj. - If the scan finishes without balance going negative, the closing direction is balanced. Reverse the string. If this was the forward pass, run the same procedure on the reversed string with
(and)swapped. If it was already the reversed pass, the twice-reversed string is a finished answer; add it to the result.
Example Walkthrough
Code
- Time Complexity: O(n^2) in the common case of a fixed number of removals: each removal costs O(n) to build the shortened string, the two scans are O(n), and the number of recursive branches is bounded by the candidate positions. The worst case stays exponential when many removals are possible, but the branching is far narrower than 2^n because only run-starting parentheses are ever removed.
- Space Complexity: O(n) beyond the output. The recursion depth equals the number of removals, at most n, and each call holds one string of length at most n. No deduplication set is allocated.
Within a run of consecutive ), removing any one of them yields the same string, so restricting removal to the first ) of each run generates each distinct string once. The lastJ bound prevents a later call from removing a ) that an earlier call already considered, so two different recursion paths can never converge on the same result. This is why no result set is needed.