# Remove Invalid Parentheses LeetCode Solution

Here, We see Remove Invalid Parentheses LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## 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: [“”]

### Remove Invalid Parentheses SolutionC++

``````class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> result;
int left_removed = 0;
int right_removed = 0;
for(auto c : s) {
if(c == '(') {
++left_removed;
}
if(c == ')') {
if(left_removed != 0) {
--left_removed;
}
else {
++right_removed;
}
}
}
helper(s, 0, left_removed, right_removed, 0, "", result);
return vector<string>(result.begin(), result.end());
}
private:
void helper(string s, int index, int left_removed, int right_removed, int pair, string path, unordered_set<string>& result) {
if(index == s.size()) {
if(left_removed == 0 && right_removed == 0 && pair == 0) {
result.insert(path);
}
return;
}
if(s[index] != '(' && s[index] != ')') {
helper(s, index + 1, left_removed, right_removed, pair, path + s[index], result);
}
else {
if(s[index] == '(') {
if(left_removed > 0) {
helper(s, index + 1, left_removed - 1, right_removed, pair, path, result);
}
helper(s, index + 1, left_removed, right_removed, pair + 1, path + s[index], result);
}
if(s[index] == ')') {
if(right_removed > 0) {
helper(s, index + 1, left_removed, right_removed - 1, pair, path, result);
}
if(pair > 0) {
helper(s, index + 1, left_removed, right_removed, pair - 1, path + s[index], result);
}
}
}
}
};```Code language: PHP (php)```

### Remove Invalid Parentheses SolutionJava

``````class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
remove(s, ans, 0, 0, new char[]{'(', ')'});
return ans;
}

public void remove(String s, List<String> ans, int last_i, int last_j,  char[] par) {
for (int stack = 0, i = last_i; i < s.length(); ++i) {
if (s.charAt(i) == par[0]) stack++;
if (s.charAt(i) == par[1]) stack--;
if (stack >= 0) continue;
for (int j = last_j; j <= i; ++j)
if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
return;
}
String reversed = new StringBuilder(s).reverse().toString();
if (par[0] == '(')
remove(reversed, ans, 0, 0, new char[]{')', '('});
else
}
}```Code language: JavaScript (javascript)```

### Remove Invalid Parentheses SolutionJavaScript

``````var removeInvalidParentheses = function(s) {
var res = [], max = 0;
dfs(s, "", 0, 0);
return res.length !== 0 ? res : [""];
function dfs(str, subRes, countLeft, maxLeft){
if(str === ""){
if(countLeft === 0 && subRes !== ""){
if(maxLeft > max)
max = maxLeft;
if(max === maxLeft && res.indexOf(subRes) === -1)
res.push(subRes);
}
return;
}
if(str[0] === '('){
dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);
}else if(str[0] === ')'){
if(countLeft > 0)
dfs(str.substring(1), subRes + ')', countLeft - 1, maxLeft);
dfs(str.substring(1), subRes, countLeft, maxLeft);
}else{
dfs(str.substring(1), subRes + str[0], countLeft, maxLeft);
}
}
};```Code language: JavaScript (javascript)```

### Remove Invalid Parentheses SolutionPython

``````class Solution(object):
def removeInvalidParentheses(self, s):
level = {s}
while True:
valid = []
for s in level:
try:
eval('0,' + filter('()'.count, s).replace(')', '),'))
valid.append(s)
except:
pass
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}``````
Scroll to Top