Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
Example 1:
Input: s = "()())()" Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()" Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25s consists of lowercase English letters and parentheses '(' and ')'.20 parentheses in s.Problem Overview: Given a string containing letters and parentheses, remove the minimum number of invalid parentheses so the resulting string becomes valid. Return all possible valid results without duplicates.
Approach 1: Breadth-First Search (BFS) (Time: O(2^n), Space: O(2^n))
The BFS approach treats each string as a node in a search graph. Start with the original string and generate the next level by removing one parenthesis at every possible position. For each generated string, check validity using a counter: increment for (, decrement for ), and ensure the count never drops below zero. The key insight is that BFS explores by number of removals. As soon as valid strings appear at a level, stop exploring deeper levels because they would require more removals than necessary. Use a queue for traversal and a set to avoid revisiting strings. This guarantees the results contain the minimum number of removals. The method works well for problems where the smallest transformation must be discovered first. Concepts rely heavily on Breadth-First Search and efficient string manipulation.
Approach 2: Depth-First Search with Backtracking (Time: O(2^n), Space: O(2^n))
This method first calculates how many left and right parentheses must be removed. Then perform a DFS that decides for each character whether to keep it or remove it. Maintain counts for open parentheses and remaining removals. When adding characters to the current path, ensure validity rules: the number of closing parentheses never exceeds opening ones. If a parenthesis is removed, decrease the appropriate removal counter. Backtracking explores all valid constructions while pruning branches that would create invalid states. A set is often used to deduplicate results. Compared with BFS, DFS generates results by constructing valid strings directly instead of exploring all intermediate states. This technique demonstrates strong understanding of backtracking and recursion pruning strategies.
Recommended for interviews: BFS is usually the most intuitive explanation because it naturally guarantees the minimum removals. Many candidates start there to show correctness reasoning. DFS with backtracking is often considered the stronger solution once you compute the exact number of parentheses that must be removed. It reduces unnecessary states and demonstrates pruning, recursion control, and deeper algorithmic thinking. Interviewers typically expect one of these two strategies with correct duplicate handling and a clear validity check.
This approach uses a BFS technique. The idea is to start with the original string and try to remove each parenthesis at each level, generating a new state each time. We are looking for the shortest valid string, hence the BFS approach ensures that we explore the minimum removal solution first.
The critical parts of the approach are:
This Python function uses a queue to explore each possible state of the string. For each invalid state, we remove one parenthesis at each position and check the new state. A visited set is used to avoid processing the same string multiple times, ensuring more efficient performance.
Time Complexity: O(2^n). For each character in the string, there are two choices: include it or not, hence exponential complexity. However, pruning the search space often reduces this in practical scenarios.
Space Complexity: O(n). Space is used to store the queue and the set of visited states.
DFS with backtracking is a common technique in situations where all combinations must be explored. In this problem, we explore each possible configuration and backtrack when we identify that no valid state can follow the current configuration.
The primary characteristics of this approach are:
This JavaScript function utilizes DFS and backtracking to explore each state's depth, leveraging a pruning strategy to skip duplicate configurations and strings that exceed the minimum removal already encountered. The use of a Set avoids duplicates in the final result.
JavaScript
Java
Time Complexity: O(2^n). Each character has two choices: include or exclude. Backtracking and pruning noticeably reduce practical complexity.
Space Complexity: O(n). Stack space utilized during recursion along with sets to store unique valid combinations.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(2^n). For each character in the string, there are two choices: include it or not, hence exponential complexity. However, pruning the search space often reduces this in practical scenarios. Space Complexity: O(n). Space is used to store the queue and the set of visited states. |
| Depth-First Search (DFS) with Backtracking | Time Complexity: O(2^n). Each character has two choices: include or exclude. Backtracking and pruning noticeably reduce practical complexity. Space Complexity: O(n). Stack space utilized during recursion along with sets to store unique valid combinations. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(2^n) | O(2^n) | Best when you want guaranteed minimum removals and a straightforward level-by-level search. |
| DFS with Backtracking | O(2^n) | O(2^n) | Preferred when pruning invalid states early and constructing valid strings directly. |
Remove Invalid Parentheses Explained using Stacks | Leetcode 301 (Valid Parentheses) Code in JAVA • Pepcoding • 38,745 views views
Watch 9 more video solutions →Practice Remove Invalid Parentheses with our built-in code editor and test cases.
Practice on FleetCode