Remove Invalid Parentheses - Solution & Explanation
Problem Statement
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 <= 25sconsists of lowercase English letters and parentheses'('and')'.- There will be at most
20parentheses ins.
Approach Overview
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.
Approach 1: Breadth-First Search (BFS)
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:
- Use a queue to store intermediate states of string removal.
- Use a set to keep track of visited states to avoid redundant work.
- Level by level, try removing each parentheses '(' or ')' and check if the remaining string is valid.
- Once a valid state is found, further remove operations are ceased at that level since BFS ensures minimum operations are performed.
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.
Complexity
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.
Approach 2: Depth-First Search (DFS) with Backtracking
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:
- Recursively explore each character, either remove or keep it, leading to a valid configuration.
- Ensure the counting of invalid parentheses removal is minimized using backtracking.
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.
Code
JavaScript
Java
Complexity
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 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Remove Invalid Parentheses Explained using Stacks | Leetcode 301 (Valid Parentheses) Code in JAVA • Pepcoding • 39,287 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Invalid Parentheses easy or hard?
Remove Invalid Parentheses Python/Java solution
How to solve Remove Invalid Parentheses in O(n)?
What is the best approach for Remove Invalid Parentheses?
Is Remove Invalid Parentheses asked at Google/Amazon/Meta?
What data structure is used in Remove Invalid Parentheses?
What is the time complexity of Remove Invalid Parentheses?
Ready to solve this problem?
Practice Remove Invalid Parentheses with our built-in code editor and test cases.
Practice on FleetCode