Last updated on January 20th, 2025 at 08:25 pm

Here, we see a Remove Invalid Parentheses LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth-First Search, Depth-First Search

Companies

Facebook

Level of Question

Hard

Remove Invalid Parentheses LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Backtracking. Backtracking is a general algorithmic technique that involves exploring all possible solutions by incrementally building candidates and abandoning a candidate as soon as it is determined that it cannot lead to a valid solution. In this case, the problem involves generating all possible valid strings by removing invalid parentheses and ensuring the result is minimal.

3. Code Implementation in Different Languages

3.1 Remove Invalid Parentheses 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);
                }
            }
        }
    }
};

3.2 Remove Invalid Parentheses 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.3 Remove Invalid Parentheses 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);
		}
	}
};

3.4 Remove Invalid Parentheses 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))}

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(2ⁿ)	O(n)
Java	O(2ⁿ)	O(n)
JavaScript	O(2ⁿ)	O(n)
Python	O(2ⁿ)	O(n * 2ⁿ)

The problem is solved using Backtracking in all implementations.
The time complexity is exponential (O(2^n)) due to the exploration of all subsets.
Space complexity varies depending on the implementation, with Python’s BFS approach being the most memory-intensive.