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())()"]
")(" -> [""]

Credits:

Because we want to remove the least number of parentheses to make the string valid, BFS is a good solution. Start from the string itself, remove one of the "(" or ")" in the string every time, if we haven't seen the string, add it to the queue. For every string polled from queue, we check if it is valid, if it is, we know we've found the longest valid string, and we set the length to current string's length, so whenever we see a string that is shorter than this length, the iteration finishes.

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();
    }