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).

Examples:

"()())()" - > ["()()()", "(())()"]
"(a)())()" - > ["(a)()()", "(a())()"]
")(" - > [""]

Solution 1: BFS，用hashset去重。每次弹出一个string，然后遍历string长度，去除一个括号，把substrings加入queue。当找到valid时，接下来queue里的不需再取substring，确保是minimum removal。

    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null) {
            return ans;
        }
        boolean found = false;
        Queue<String> queue = new LinkedList<>();
        Set<String> hashset = new HashSet<>();
        queue.offer(s);
        hashset.add(s);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            if (isValid(cur)) {
                ans.add(cur);
                found = true;
            }
            if (found) {
                continue;
            }
            for (int i = 0; i < cur.length(); i++) {
                if (cur.charAt(i) != '(' && cur.charAt(i) != ')') {
                    continue;
                }
                String substring = cur.substring(0, i) + cur.substring(i + 1);
                if (!hashset.contains(substring)) {
                    queue.offer(substring);
                    hashset.add(substring);
                }
            }
        }
        return ans;
    }
    private boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            } else if (c == ')'){
                if (count == 0) {
                    return false;
                }
                count--;
            }
        }
        return count == 0;
    }

Solution 2: DFS

1.Limit max removalrmLandrmRfor backtracking boundary. Otherwise it will exhaust all possible valid substrings, not shortest ones.

1. Scan from left to right, avoiding invalid strs (on the fly) by checking num ofopenparens.

2. If it's '(', either use it, or remove it.

3. If it's '(', either use it, or remove it.

4. Otherwise just append it.

public List<String> removeInvalidParentheses(String s) {
    int rmL = 0, rmR = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            rmL++;
        } else if (s.charAt(i) == ')') {
            if (rmL != 0) {
                rmL--;
            } else {
                rmR++;
            }
        }
    }
    Set<String> res = new HashSet<>();
    dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);
    return new ArrayList<String>(res);
}

public void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open) {
    if (rmL < 0 || rmR < 0 || open < 0) {
        return;
    }
    if (i == s.length()) {
        if (rmL == 0 && rmR == 0 && open == 0) {
            res.add(sb.toString());
        }        
        return;
    }

    char c = s.charAt(i); 
    int len = sb.length();

    if (c == '(') {
        dfs(s, i + 1, res, sb, rmL - 1, rmR, open);            // not use (
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1);       // use (

    } else if (c == ')') {
        dfs(s, i + 1, res, sb, rmL, rmR - 1, open);                // not use  )
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1);          // use )

    } else {
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);    
    }
    //backtracking
    sb.setLength(len);        
}