Solution

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();

        int maxLen = -1;
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(s);
        visited.add(s);
        while (!queue.isEmpty()) {
            String current = queue.poll();
            if (isValid(current)) {
                if (current.length() >= maxLen) {
                    maxLen = current.length();
                    result.add(current);
                }
            }

            for (int i = 0; i < current.length(); i++) {
                if (current.charAt(i) != '(' && current.charAt(i) != ')') {
                    continue;
                }
                String subStr = current.substring(0, i) + current.substring(i + 1);
                if (!visited.contains(subStr) && (maxLen == -1 || subStr.length() >= maxLen)) {
                    queue.add(subStr);
                    visited.add(subStr);
                }
            }
        }
        return result;
    }
    private boolean isValid(String current) {
        int open = 0;
        for (int i = 0; i < current.length(); i++) {
            if (current.charAt(i) == '(') {
                open++;
            } else if (current.charAt(i) == ')') {
                open--;
            }
            if (open < 0) {
                return false;
            }
        }
        return open == 0;
    }
}