from collections import deque
class Solution:
def removeInvalidParentheses(self, s: str):
res = []
visited = set()
queue = deque([s])
found = False
while queue:
curr = queue.popleft()
if self.isValid(curr):
res.append(curr)
found = True
if found:
continue
for i in range(len(curr)):
if curr[i] not in ('(', ')'):
continue
next_str = curr[:i] + curr[i+1:]
if next_str not in visited:
visited.add(next_str)
queue.append(next_str)
return res
def isValid(self, s):
count = 0
for c in s:
if c == '(':
count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return count == 0
#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> visited;
queue<string> q;
q.push(s);
visited.insert(s);
bool found = false;
while (!q.empty()) {
string curr = q.front();
q.pop();
if (isValid(curr)) {
res.push_back(curr);
found = true;
}
if (found) continue;
for (int i = 0; i < curr.size(); ++i) {
if (curr[i] != '(' && curr[i] != ')') continue;
string next = curr.substr(0, i) + curr.substr(i+1);
if (visited.find(next) == visited.end()) {
visited.insert(next);
q.push(next);
}
}
}
return res;
}
bool isValid(string s) {
int count = 0;
for (char c : s) {
if (c == '(') count++;
else if (c == ')') {
count--;
if (count < 0) return false;
}
}
return count == 0;
}
};
import java.util.*;
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> res = 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 curr = queue.poll();
if (isValid(curr)) {
res.add(curr);
found = true;
}
if (found) continue;
for (int i = 0; i < curr.length(); i++) {
if (curr.charAt(i) != '(' && curr.charAt(i) != ')') continue;
String next = curr.substring(0, i) + curr.substring(i+1);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
return res;
}
private boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') count++;
else if (c == ')') {
count--;
if (count < 0) return false;
}
}
return count == 0;
}
}
/**
* @param {string} s
* @return {string[]}
*/
var removeInvalidParentheses = function(s) {
let res = [];
let visited = new Set();
let queue = [s];
let found = false;
while (queue.length) {
let curr = queue.shift();
if (isValid(curr)) {
res.push(curr);
found = true;
}
if (found) continue;
for (let i = 0; i < curr.length; i++) {
if (curr[i] !== '(' && curr[i] !== ')') continue;
let next = curr.slice(0, i) + curr.slice(i+1);
if (!visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
}
return res;
};
function isValid(s) {
let count = 0;
for (let c of s) {
if (c === '(') count++;
else if (c === ')') {
count--;
if (count < 0) return false;
}
}
return count === 0;
}
Given a string s that contains parentheses '(' and ')' as well as other characters, your task is to remove the minimum number of invalid parentheses in order to make the input string valid. You must return all possible results (not just one), and you may return the answers in any order.
'(' has a corresponding closing parenthesis ')' and vice versa, with proper nesting.
Example:
Input: s = "()())()"
Output: ["(())()", "()()()"]
At first glance, you might think about brute-forcing every possible way to remove parentheses and then checking which results are valid. However, this approach is not practical because the number of possible strings grows exponentially as you remove characters.
To optimize, we want to remove the minimum number of parentheses to make the string valid. This means that as soon as we find valid strings with a certain number of removals, we don't need to check strings with more removals.
A good analogy is searching for the shortest path in a maze: once you find a way out with the least steps, you don't need to keep looking for longer paths.
This suggests using Breadth-First Search (BFS) to explore all possible strings by removing one parenthesis at a time, level by level. The first valid strings found are guaranteed to have the minimal number of removals.
Let's walk through the input s = "()())()":
()())()
)())()()()()()()())()()()))()()())()()())(After removing each, we check validity:
(())() and ()()() are valid at this level.
So, the result is ["(())()", "()()()"].
O(2^n) time and space, where n is the length of s.2^n substrings in the worst case, but stops as soon as valid strings are found at the minimum removal level.O(2^n) due to the queue and visited set, but only for distinct substrings generated.The key to solving "Remove Invalid Parentheses" efficiently is to use Breadth-First Search (BFS) to explore all possible strings by removing one parenthesis at a time, and to stop as soon as the first valid results are found. This ensures that only the minimal number of removals are performed. Using a visited set prevents redundant work, and a helper function efficiently checks the validity of each string. This approach elegantly balances completeness (finding all solutions) with efficiency, making it both practical and robust.