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:

Count the minimum amount of parentheses we need to remove.

Using dfs to find all the answer. (avoid duplication)

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        //count the min amount need to be remove
        int l = 0;
        int r = 0;
        for (char ss : s.toCharArray()) {
            if (ss == '(') {
                l++;
            } else if (ss == ')') {
                if (l == 0) {
                    r++;
                } else {
                    l--;
                }
            }
        }
        
        List<String> res = new ArrayList<>();
        dfs(s, 0, l, r, res);
        return res;
    }
    
    private void dfs(String s, int startIndex, int l, int r, List<String> res) {
        //end condition, nothing to remove
        if (l == 0 && r == 0) {
            if (isValid(s)) {
                res.add(s);
            }
            return;
        }
        
        for (int i = startIndex; i < s.length(); i++) {
            //avoid duplication
            if (i != startIndex && s.charAt(i) == s.charAt(i - 1)) {
                continue;
            }
            
            if (s.charAt(i) == '(' || s.charAt(i) == ')') {
                String cur = s;
                // cur.remove(i);
                cur = cur.substring(0, i) + cur.substring(i + 1);
                //recursive
                if (s.charAt(i) == ')' && r > 0) {
                    dfs(cur, i, l, r - 1, res);
                } else if (s.charAt(i) == '(' && l > 0) {
                    dfs(cur, i, l - 1, r, res);
                }
            }
        }
    }
    
    private boolean isValid(String s) {
        int count = 0;
        for (char ss : s.toCharArray()) {
            if (ss == '(') {
                count++;
            }
            if (ss == ')') {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}

Time complexity: O(2^n)

Space complexity: O(n)