301. Remove Invalid Parentheses - cocoder39/coco39_LC GitHub Wiki

301. Remove Invalid Parentheses

notes 2024:

high level thought: using backtrack to build valid string

optimizations:

  1. instead of deciding on whether to drop each individual parentheses, we can be smart. we can first check how many left and right parentheses are required to be removed. Using that as guideline to optimize backtrack
  2. there could be duplicated results, so using a set to dedep
  3. once a string is built out, we can evaluate if it is valid. An optimization is to ensure only valid string can be built during building process. We achieve this by recording how many open parentheses are in the final string

time complexity O(2 ^ N) since we have 2 options for each parenthesis

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left, right = 0, 0
        for ch in s:
            if ch == '(':
                left += 1
            elif ch == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1

        res = set()
        self.getValidParentheses(s, left, right, 0, '', 0, res)
        return list(res)
    
    def getValidParentheses(self, s, left, right, open, cur_str, cur_idx, res):
        if left == 0 and right == 0 and cur_idx == len(s) and open == 0:
            res.add(cur_str)
        
        if left < 0 or right < 0 or cur_idx >= len(s):
            return

        if s[cur_idx] == '(' and left > 0:
            self.getValidParentheses(s, left-1, right, open, cur_str, cur_idx+1, res)
        elif s[cur_idx] == ')' and right > 0:
            self.getValidParentheses(s, left, right-1, open, cur_str, cur_idx+1, res)

        if s[cur_idx] == '(':
            self.getValidParentheses(s, left, right, open+1, cur_str+s[cur_idx], cur_idx+1, res)
        elif s[cur_idx] == ')' and open > 0:
            self.getValidParentheses(s, left, right, open-1, cur_str+s[cur_idx], cur_idx+1, res)
        else:
            self.getValidParentheses(s, left, right, open, cur_str+s[cur_idx], cur_idx+1, res)

suboptimal solution which validate every built result

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left, right = 0, 0
        for ch in s:
            if ch == '(':
                left += 1
            elif ch == ')':
                if left > 0:
                    left -= 1
                else:
                    right += 1

        res = set()  # Use a set to avoid duplicates
        self.getValidParentheses(s, left, right, '', 0, res)
        return list(res)
    
    def getValidParentheses(self, s, left, right, cur_str, cur_idx, res):
        if left == 0 and right == 0 and cur_idx == len(s) and self.isValidParentheses(cur_str):
            res.add(cur_str)
        
        if left < 0 or right < 0 or cur_idx >= len(s):
            return

        self.getValidParentheses(s, left, right, cur_str + s[cur_idx], cur_idx+1, res)  # Keep current character
        if s[cur_idx] == '(' and left > 0:
            self.getValidParentheses(s, left-1, right, cur_str, cur_idx+1, res)  # Skip current '('
        elif s[cur_idx] == ')' and right > 0:
            self.getValidParentheses(s, left, right-1, cur_str, cur_idx+1, res)  # Skip current ')'
        

    def isValidParentheses(self, s):
        stack = []
        for ch in s:
            if ch == '(':
                stack.append('(')
            elif ch == ')':
                if stack and stack[-1] == '(':
                    stack.pop()
                else:
                    return False
        return len(stack) == 0

======================================================================= tips:

  • use vector<string>(res.begin(), res.end()) to copy std::unordered_set to std::vector
  • it is not allowed to pass "" to a string&
  • if use string&, remember to use pop_back() after using push_back(), think about how backtracking works in dfs

O(2^N) where N is s.length()

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        unordered_set<string> res;
        string path;
        
        int rml = 0, rmr = 0; //number of left parentheses and right parentheses that need be removed
        for (auto c : s) {
            if (c == '(')
                rml++;
            else if (c == ')') {
                if (rml != 0)
                    rml--;
                else
                    rmr++;
            }
        }

        dfs(s, 0, res, path, rml, rmr, 0);       
        return vector<string>(res.begin(), res.end()); 
    }
private:
    void dfs(string& s, int start, unordered_set<string>& res, string& path, int rml, int rmr, int open) {
        if (rml == 0 && rmr == 0 && open == 0 && start == s.length()) {
            res.insert(path);
            return;
        }
        if (rml < 0 || rmr < 0 || open < 0 || start >= s.length())
            return;
        
        char c = s[start];
        if (c == '(') {
            dfs(s, start + 1, res, path, rml - 1, rmr, open);
            path.push_back(c);
            dfs(s, start + 1, res, path, rml, rmr, open + 1);
            path.pop_back();
        }
        else if (c == ')') {
            dfs(s, start + 1, res, path, rml, rmr - 1, open);
            path.push_back(c);
            dfs(s, start + 1, res, path, rml, rmr, open - 1);
            path.pop_back();
        }
        else { //alphabet
            path.push_back(c);
            dfs(s, start + 1, res, path, rml, rmr, open);
            path.pop_back();
        }
    }
};

above method uses set to get rid of duplicates. Meanwhile, we can use boolean array to record the removed state of each char in s, for a series of '(' or a series of ')' to be removed, we only remove the first one with that series. We use this method to get rid of duplication in permutation before.

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int rml = 0, rmr = 0;
        for (c : s) {
            if (c == '(') {
                rml++;
            } else if (c == ')') {
                if (rml > 0) {
                    rml--;
                } else {
                    rmr++;
                }
            }
        }
        
        vector<string> res;
        string cur;
        vector<bool> removed(s.length());
        dfs(res, cur, s, 0, 0, rml, rmr, removed);
        return res;
    }
private:
    void dfs(vector<string>& res, string& cur, string& s, int start, int open, int rml, int rmr, vector<bool>& removed) {
        if (start == s.length() && open == 0 && rml == 0 && rmr == 0) {
            res.push_back(cur);
            return;
        } else if (start == s.length() || open < 0 || rml < 0 || rmr < 0) {
            return;
        }
        
        char c = s[start];
        if (c == '(') {
            if (start == 0 || removed[start - 1] || s[start - 1] != '(') {
                removed[start] = true;
                dfs(res, cur, s, start + 1, open, rml - 1, rmr, removed); //remove first '(' from a series of '('
                removed[start] = false;
            }
            cur.push_back(c);
            dfs(res, cur, s, start + 1, open + 1, rml, rmr, removed); //keep '('
            cur.pop_back();
        } else if (c == ')') {
            if (start == 0 || removed[start - 1] || s[start - 1] != ')') {
                removed[start] = true;
                dfs(res, cur, s, start + 1, open, rml, rmr - 1, removed); //remove ')'
                removed[start] = false;
            }
            cur.push_back(c);
            dfs(res, cur, s, start + 1, open - 1, rml, rmr, removed); //keep ')'
            cur.pop_back();
        } else {
            cur.push_back(c);
            dfs(res, cur, s, start + 1, open, rml, rmr, removed);
            cur.pop_back();
        }
    }
};

return an valid result, not all results.

string removeInvalidParentheses(string s) {
        int i = 0, rml = 0;
        for (int j = 0; j < s.length(); j++) {
            if (s[j] == '(') {
                rml++;
                s[i++] = s[j];
            } else if (s[j] == ')') {
                if (rml > 0) {
                    rml--;
                    s[i++] = s[j];
                } 
            } else {
                s[i++] = s[j];
            }
        }
        
        int k = i - 1, rmr = 0;
        for (int j = i - 1; j >= 0; j--) {
            if (s[j] == ')') {
                rmr++;
                s[k--] = s[j];
            } else if (s[j] == '(') {
                if (rmr > 0) {
                    rmr--;
                    s[k--] = s[j];
                } 
            } else {
                s[k--] = s[j];
            }
        }
        
        string res = s.substr(k + 1, (i - 1) - (k + 1) + 1);
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️