BackTrackingProblem 4 of 19
Remove Invalid Parentheses
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 all possible results. The order of the output does not matter.
Example:
Input: s = "()())()"
Output: ["(())()", "()()()" ]
Input: s = "(a)())()"
Output: ["(a())()", "(a)()()" ]
Input: s = ")("
Output: [""]
Explanation: We need to remove minimum parentheses to make valid strings.
Approach 1: Brute Force (Generate All Subsets)
Intuition
Generate all possible subsets by including or excluding each character. Among valid strings, keep those with maximum length (minimum removals).
Algorithm
- Generate all possible subsets of the string
- Check validity of each subset
- Track the maximum length of valid strings
- Return all valid strings with maximum length
java
import java.util.*;
class Solution {
private int maxLen = 0;
public boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') count++;
else if (c == ')') {
if (count == 0) return false;
count--;
}
}
return count == 0;
}
public void generate(String s, int index, String current, Set<String> result) {
if (index == s.length()) {
if (isValid(current)) {
if (current.length() > maxLen) {
maxLen = current.length();
result.clear();
result.add(current);
} else if (current.length() == maxLen) {
result.add(current);
}
}
return;
}
// Exclude current character (only if it's a parenthesis)
char c = s.charAt(index);
if (c == '(' || c == ')') {
generate(s, index + 1, current, result);
}
// Include current character
generate(s, index + 1, current + c, result);
}
public List<String> removeInvalidParentheses(String s) {
Set<String> result = new HashSet<>();
maxLen = 0;
generate(s, 0, "", result);
return new ArrayList<>(result);
}
}Complexity Analysis
- Time Complexity: O(2^n × n) - 2^n subsets, O(n) to validate each
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (BFS Level by Level)
Intuition
Use BFS to explore strings level by level, where each level represents removing one more character. The first level where we find valid strings is the answer (minimum removals).
Algorithm
- Start with the original string in a queue
- For each string, check if it's valid
- If valid, add to result and mark level complete
- If not valid and level not complete, generate all strings by removing one parenthesis
- Use a set to avoid duplicates
java
import java.util.*;
class Solution {
public boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') count++;
else if (c == ')') {
if (count == 0) return false;
count--;
}
}
return count == 0;
}
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(s);
visited.add(s);
boolean found = false;
while (!queue.isEmpty()) {
String current = queue.poll();
if (isValid(current)) {
result.add(current);
found = true;
}
// If we found valid strings at this level, don't go deeper
if (found) continue;
// Generate all possible strings by removing one parenthesis
for (int i = 0; i < current.length(); i++) {
char c = current.charAt(i);
if (c != '(' && c != ')') continue;
String next = current.substring(0, i) + current.substring(i + 1);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(2^n) - In worst case, explore all subsets
- Space Complexity: O(2^n) - For visited set and queue
Approach 3: Optimal (Count-based Backtracking)
Intuition
First, count the minimum number of '(' and ')' to remove. Then use backtracking to try removing exactly that many, pruning invalid branches early.
java
import java.util.*;
class Solution {
private Set<String> result = new HashSet<>();
public void backtrack(String s, int index, int openCount, int closeCount,
int openRem, int closeRem, StringBuilder current) {
if (index == s.length()) {
if (openRem == 0 && closeRem == 0) {
result.add(current.toString());
}
return;
}
char c = s.charAt(index);
int len = current.length();
// Case 1: Remove current character
if (c == '(' && openRem > 0) {
backtrack(s, index + 1, openCount, closeCount,
openRem - 1, closeRem, current);
} else if (c == ')' && closeRem > 0) {
backtrack(s, index + 1, openCount, closeCount,
openRem, closeRem - 1, current);
}
// Case 2: Keep current character
current.append(c);
if (c != '(' && c != ')') {
backtrack(s, index + 1, openCount, closeCount,
openRem, closeRem, current);
} else if (c == '(') {
backtrack(s, index + 1, openCount + 1, closeCount,
openRem, closeRem, current);
} else if (closeCount < openCount) {
backtrack(s, index + 1, openCount, closeCount + 1,
openRem, closeRem, current);
}
current.deleteCharAt(len);
}
public List<String> removeInvalidParentheses(String s) {
int openRem = 0, closeRem = 0;
for (char c : s.toCharArray()) {
if (c == '(') openRem++;
else if (c == ')') {
if (openRem > 0) openRem--;
else closeRem++;
}
}
result.clear();
backtrack(s, 0, 0, 0, openRem, closeRem, new StringBuilder());
return new ArrayList<>(result);
}
}Complexity Analysis
- Time Complexity: O(2^n) - Each character can be kept or removed
- Space Complexity: O(n) - Recursion stack
Key Takeaways
- BFS for Minimum: BFS naturally finds minimum removals by exploring level by level
- Count-based Pruning: Pre-counting required removals enables effective pruning
- Validity Check: Track open/close count to validate parentheses
- Duplicate Handling: Use HashSet to avoid duplicate results
- LeetCode #301: Hard problem - Remove Invalid Parentheses
- Early Termination: Stop exploring deeper once valid strings are found at current level