Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

&nbsp;
Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]


Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]


Example 3:

Input: s = ")("
Output: [""]


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 25
	s consists of lowercase English letters and parentheses '(' and ')'.
	There will be at most 20 parentheses in s.


class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        ## RC ##
        ## APPROACH : BACK-TRACKING ##
        ## Similar to Leetcode 32. Longest Valid Parentheses ##
        ## LOGIC ##
        #   1. use stack to find invalid left and right braces.
        #   2. if its close brace at index i , you can remove it directly to make it valid and also you can also remove any of the close braces before that i.e in the range [0,i-1]
        #   3. similarly for open brace, left over at index i, you can remove it or any other open brace after that i.e [i+1, end]
        #   4. if left over braces are more than 1 say 2 close braces here, you need to make combinations of all 2 braces before that index and find valid parentheses.
        #   5. so, we count left and right invalid braces and do backtracking removing them
        
		## TIME COMPLEXITY : O(2^N) ## (each brace has 2 options: exits or to be removed)
		## SPACE COMPLEXITY : O(N) ##

        def isValid(s):
            stack = []
            for i in range(len(s)):
                if( s[i] == '(' ):
                    stack.append( (i,'(') )
                elif( s[i] == ')' ):
                    if(stack and stack[-1][1] == '('):
                        stack.pop()
                    else:
                        stack.append( (i,')') )         # pushing invalid close braces also
            return len(stack) == 0, stack
        
        
        def dfs( s, left, right):
            visited.add(s)
            if left == 0 and right == 0 and isValid(s)[0]:  res.append(s)
            for i, ch in enumerate(s):
                if ch != '(' and ch != ')': continue                                    # if it is any other char ignore.
                if (ch == '(' and left == 0) or (ch == ')' and right == 0): continue    # if left == 0 then removing '(' will only cause imbalance. Hence, skip.
                if s[:i] + s[i+1:] not in visited:
                    dfs( s[:i] + s[i+1:], left - (ch == '('), right - (ch == ')') )
        
        stack = isValid(s)[1]
        lc = sum([1 for val in stack if val[1] == "("]) # num of left braces
        rc = len(stack) - lc
        
        res, visited = [], set()
        dfs(s, lc, rc)
        return res
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ans=new ArrayList<>();
        HashSet<String> set=new HashSet<String>();
        
        int minBracket=removeBracket(s);
        getAns(s, minBracket,set,ans);
        
        return ans;
    }
    
    public void getAns(String s, int minBracket, HashSet<String> set, List<String> ans){
        if(set.contains(s)) return;
        
        set.add(s);
        
        if(minBracket==0){
            int remove=removeBracket(s);   
            if(remove==0) ans.add(s);
            return;
        }
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!='(' && s.charAt(i)!=')') continue;
            String L=s.substring(0,i);
            String R=s.substring(i+1);
            
            if(!set.contains(L+R)) getAns(L+R,minBracket-1,set,ans);
        }
    }
    
    public int removeBracket(String s){
        Stack<Character> stack=new Stack<>();
        
        for(int i=0;i<s.length();i++){
            char x=s.charAt(i);
            
            if(x=='(') stack.push(x);
            else if(x==')'){
                if(!stack.isEmpty() && stack.peek()=='(') stack.pop();
                else stack.push(x);
            } 
        }
        return stack.size();
    }
}
class Solution {
public:
    void back_tracking(vector<string>& res, string cus, int lp, int rp, int idx) {
        if (!lp && !rp) {
            int invalid = 0;
            bool flag = true;
            for (int i = 0; i < cus.size(); i++) {
                if (cus[i] == '(')
                    invalid++;
                else if (cus[i] == ')') {
                    invalid--;
                    if (invalid < 0) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag)
                res.emplace_back(cus);
            return;
        }
        
        for (int i = idx; i < cus.size(); i++) {
            if (i != idx && cus[i] == cus[i - 1])
                continue;
            
            if (lp + rp > cus.size() - i)
                return;
            
            if (lp && cus[i] == '(')
                back_tracking(res, cus.substr(0, i) + cus.substr(i + 1), lp - 1, rp, i);
            
            if (rp && cus[i] == ')')
                back_tracking(res, cus.substr(0, i) + cus.substr(i + 1), lp, rp - 1, i);
        }
    }
    
    vector<string> removeInvalidParentheses(string s) {
        int left_p = 0;
        int right_p = 0;
        for (auto& ch : s) {
            if (ch == '(')
                left_p++;
            else if (ch == ')') {
                if (left_p > 0)
                    left_p--;
                else
                    right_p++;
            }
        }
        vector<string> res;
        back_tracking(res, s, left_p, right_p, 0);
        return res;
    }
};
var removeInvalidParentheses = function(s) {
    const isValid = (s) => {
        const stack = [];
        for(let c of s) {
            if(c == '(') stack.push(c);
            else if(c == ')') {
                if(stack.length && stack.at(-1) == '(')
                    stack.pop();
                else return false;
            }
        }
        return stack.length == 0;
    }

    const Q = [s], vis = new Set([s]), ans = [];
    let found = false;
    while(Q.length) {
        const top = Q.shift();
        if(isValid(top)) {
            ans.push(top);
            found = true;
        }
        if(found) continue;
        for(let i = 0; i < top.length; i++) {
            if(!'()'.includes(top[i])) continue;

            const str = top.slice(0, i) + top.slice(i + 1);
            if(!vis.has(str)) {
                Q.push(str);
                vis.add(str);
            }
        }
    }
    if(ans.length == 0) return [''];
    return ans;
};
Remove Invalid Parentheses