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

Examples:

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

The problem uses a BFS approach. Each iteration we remove one parenthesis from the string. Check if it is valid, if it is, then the length of the substring is the length of all valid answers (all shorter substring requires removing more parenthesis).

public List removeInvalidParentheses(String s) {
        List validParentheses = new ArrayList<>();
        Queue queue = new LinkedList<>();
        Set visited = new HashSet<>();
        queue.add(s);
        int done = -1;
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            if (curr.length() < done)
                break;
            if (isValid(curr)) {
                validParentheses.add(curr);
                done = curr.length();
            } else {
                for (int i = 0; i < curr.length(); i++) {
                    if ("()".indexOf(curr.charAt(i)) < 0)
                        continue;
                    String next = curr.substring(0, i) + curr.substring(i + 1);
                    if (visited.add(next)) {
                        queue.add(next);
                    }
                }
            }
        }
        return validParentheses;

    }
    
    private boolean isValid(String s) {
        Stack left = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left.add(i);
            } else if (s.charAt(i) == ')') {
                if (left.isEmpty())
                    return false;
                else
                    left.pop();
            }
        }
        return left.isEmpty();
    }