Remove Invalid Parentheses

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

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

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

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

Solution:

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int[] valid = validate(s);
        int left = valid[0];
        int right = valid[1];
        List<String> result = new ArrayList();
        Set<String> visited = new HashSet();
        dfs(s, left, right, result, visited);
        return result;
    }
    
    private void dfs(String s, int left, int right, List<String> result, Set<String> visited) {
        if (!visited.add(s)) return;
        if (left == 0 && right == 0) {
            int[] valid = validate(s);
            if (valid[0] == 0 && valid[1] == 0) {
                result.add(s);
            }
            return;
        }
        for (int i = 0; i < s.length(); i ++) {
            if (i > 0 && s.charAt(i) == s.charAt(i - 1)) continue;
            StringBuilder sb = new StringBuilder(s);
            if (s.charAt(i) == '(' && left > 0) {
                sb.deleteCharAt(i);
                dfs(sb.toString(), left - 1, right, result, visited);
            }
            if (s.charAt(i) == ')' && right > 0) {
                sb.deleteCharAt(i);
                dfs(sb.toString(), left, right - 1, result, visited);
            }
        }
    }
    
    private int[] validate(String s) {
        int left = 0;
        int right = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                left ++;
            }
            if (c == ')') {
                if (left > 0) {
                    left --;
                } else {
                    right ++;
                }
            }
        }
        return new int[]{left, right};
    }
}