Last updated on July 20th, 2024 at 04:09 am

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

Topics

Breadth-First Search, Depth-First Search

Companies

Facebook

Level of Question

Hard

Remove Invalid Parentheses 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: [“”]

1. Remove Invalid Parentheses Solution C++

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);
                }
            }
        }
    }
};

2. Remove Invalid Parentheses Solution Java

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
        ans.add(reversed);
}
}

3. Remove Invalid Parentheses Solution JavaScript

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);
		}
	}
};

4. Remove Invalid Parentheses Solution Python

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))}