301. Remove Invalid Parentheses

Problem description:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: “()())()”
Output: [“()()()”, “(())()”]
Example 2:

Input: “(a)())()”
Output: [“(a)()()”, “(a())()”]
Example 3:

Input: “)(“
Output: [“”]

Solution:

Question can ask in interview:

1. what is invalid, if contains other characters or digits, will it be valid?
2. Input type, string
3. Output type, should be vector
4. time/space complexity restriction

Solution:
We’re trying to make it valid, we need to remove a ‘)’. And should remove the extra parentheses by counting redundant left or right parentheses. Then use dfs to check if the string is valid or not.

1. Check input is valid or not by using variable to count left parentheses and right parentheses.
   count('(') >= count(')'), i< n-1. Before reach to end of string, count of left parentheses should always be greater or equal than right parentheses. Because if right has more then left, it would be invalid.
   count('(') == count(')'), i == n-1. When reach to the end, if it’s a valid string, number of left == number of right.

2. Use dfs to check “if we remove extra parentheses, the string is valid or not”.

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        '''
        backtracking
        l, r in func to denote the remaining need to delete
        what is l, r? invalid count of left and right 
        note we need to skip duplicate to avoid situation like "()())()"
        '''
        l, r= 0, 0
        for i in range(len(s)):
            if s[i] == '(':
                l += 1
            elif s[i] == ')':
                if l == 0:
                    r += 1
                else:
                    l -= 1
        
        def isValid(s):
            l, r = 0, 0
            for w in s:
                if w == '(':
                    l += 1
                elif w == ')':
                    r += 1
                if r > l:
                    return False
            return l == r
        
        # res = set()
        res = []
        def backtrack(s, idx, l, r, res):
            if l == 0 and r == 0:
                if isValid(s):
                    # print(s)
                    # res.add(s)
                    res.append(s)
                return
            # print(s, idx, l, r, res)
            for i in range(idx, len(s)):
                if i != idx and s[i] == s[i-1]: continue
                if l > 0 and s[i] == '(':
                    backtrack(s[:i]+s[i+1:], i, l-1, r, res)
                if r > 0 and s[i] == ')':
                    backtrack(s[:i]+s[i+1:], i, l, r-1, res)
        
        
        backtrack(s, 0, l, r, res)
        return res
        # return [i for i in res]

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        /*
        
        1. count redundant left or right parentheses
        2. dfs to find after remove parentheses, the string would be valid or not. One thing to notice is to skip duplicate character

        */
        vector<string> res;
        int i= 0, l= 0, r= 0;
        for(auto c: s){
            if(c == '(')
                l++;
            if(c == ')'){
                if(l == 0) r++;
                else l--;
            }
        }
        
        helper(s, 0, l, r, res);
        return res;
    }
    
    void helper(string s, int start, int cnt1, int cnt2, vector<string>& res) {
        if(cnt1 == 0 && cnt2 == 0){
            if(isValid(s)) res.push_back(s);
            return;
        }
        for(int i= start; i< s.length(); i++){
            //check duplicate
            if(i != start && s[i] == s[i-1]) continue;
            if(cnt1 > 0 && s[i] == '(') 
                helper(s.substr(0, i)+ s.substr(i+1), i, cnt1-1, cnt2, res);
            if(cnt2 > 0 && s[i] == ')')
                helper(s.substr(0, i)+ s.substr(i+1), i, cnt1, cnt2-1, res);
        }
    }
    
    bool isValid(string s){
        int left= 0, right= 0;
        for(auto c: s){
            if(c == '('){
                left++;
            }
            if(c == ')')
                right++;
            
            if(right> left) return false;
        }
        return left == right;
    }
};

time complexity: $O(2 ^ {l+r})$
space complexity: $O((l+r)^2)$ ~ $O(n^2)$

reference:
https://goo.gl/KgYdwq
https://goo.gl/p61yqa

second time:

The same idea.

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        /*
        1. count how many invalid '(' or ')'
        2. use dfs to get different output
            isValid function
        */
        vector<string> res;
        
        stack<char> stk;
        int i= 0;
        int left= 0, right= 0;
        while(i< s.length()){
            if(s[i] == '(')
                left++;
            if(s[i] == ')'){
                if(left== 0)
                    right++;
                else
                    left--;
            }
            i++;
        }
        dfs(res, s, left, right, 0);
        return res;
    }
    
    void dfs(vector<string>& res, string tmp, int left, int right, int start){
        if(left == 0 && right == 0){
            if(isValid(tmp))
                res.push_back(tmp);
            return;
        }
        for(int i= start; i< tmp.length(); i++){
            //skip duplicate element
            if(i != start && tmp[i] == tmp[i-1]) continue;
            if(left>0 && tmp[i]== '(') 
                dfs(res, tmp.substr(0, i)+ tmp.substr(i+1), left-1, right, i);
            if(right>0 && tmp[i] == ')') 
                dfs(res, tmp.substr(0, i)+ tmp.substr(i+1), left, right-1, i);
        }
        
    }
    
    
    bool isValid(string s){
        int left= 0, right= 0, i= 0;
        while(i< s.length()){
            if(s[i] == '(')
                left++;
            if(s[i] == ')')
                left--;
            if(left< 0) return false;
            i++;
        }
        return left == 0;
    }
    
};