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:
Special thanks to @hpplayer for adding this problem and creating all test cases.

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new LinkedList<>();
        if (s == null) {
            return res;
        }
        //Remove proceeding ")".
        int i = 0;
        while (i < s.length() && s.charAt(i) != '(') i++;
        s = s.substring(0, i).replace(")", "") + ((i == s.length())?"" : s.substring(i));

        //Remove trailing "("
        int j = s.length() - 1;
        while (j >= 0 && s.charAt(j) != ')') j--;
        s = s.substring(0, j+1) + ((j == s.length()-1)? "" : s.substring(j+1).replace("(", ""));

        HashSet<String> visited = new HashSet<>();
        visited.add(s);
        LinkedList<String> queue = new LinkedList<>();
        queue.add(s);
        boolean isValid = false;
        while (!queue.isEmpty() && !isValid) {
            int count = queue.size();
            while (count-- > 0) {
                String str = queue.poll();
                if (isValid(str)) {
                    res.add(str);
                    isValid = true;
                } else {
                    for (int position = 0; position < str.length(); position++) {
                        if (str.charAt(position) != '(' && str.charAt(position) != ')') continue;
                        String nextStr = str.substring(0, position) + str.substring(position + 1);
                        if (visited.add(nextStr)) {
                            queue.add(nextStr);
                        }
                    }
                }
            }
        }
        return res;
    }
 
    private boolean isValid(String str) {
        int left = 0;
        for (char c : str.toCharArray()) {
            if (c == '(') {
                left++;
            } else if (c == ')') {
                left--;
                if (left < 0) return false;
            }
        }
        return left == 0;
    }
}

=================