301. Remove Invalid Parentheses

// LeetCode URL: https://leetcode.com/problems/remove-invalid-parentheses/
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * BFS
 *
 * Refer:
 * https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/Share-my-Java-BFS-solution
 *
 * Time Complexity: O(n * 2^n).
 *
 * In BFS we handle the states level by level, in the worst case, we need to
 * handle all the levels, we can analyze the time complexity level by level and
 * add them up to get the final complexity.
 *
 * On the first level, there's only one string which is the input string s,
 * let's say the length of it is n, to check whether it's valid, we need O(n)
 * time. On the second level, we remove one ( or ) from the first level, so
 * there are C(n, n-1) new strings, each of them has n-1 characters, and for
 * each string, we need to check whether it's valid or not, thus the total time
 * complexity on this level is (n-1) x C(n, n-1). Come to the third level, total
 * time complexity is (n-2) x C(n, n-2), so on and so forth...
 *
 * Finally we have this formula:
 *
 * T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1).
 *
 *
 * Space Complexity: O(n/2 * (n C (n/2))). Upper bound = O(n * (2*e)^(n/2))
 *
 * At n/2 level, the space required will be maximum. Refer below link for proof
 * and calculation of nCk
 * https://www.johndcook.com/blog/2008/11/10/bounds-on-binomial-coefficients/
 */
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        ArrayList<String> result = new ArrayList<>();
        if (s == null) {
            return result;
        }

        Queue<String> queue = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        boolean foundValid = false;
        queue.offer(s);
        visited.add(s);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                String cur = queue.poll();

                if (isValid(cur)) {
                    result.add(cur);
                    foundValid = true;
                }
                if (foundValid) {
                    continue;
                }

                for (int j = 0; j < cur.length(); j++) {
                    if (cur.charAt(j) != '(' && cur.charAt(j) != ')') {
                        continue;
                    }
                    String newCur = cur.substring(0, j) + cur.substring(j + 1);
                    if (!visited.contains(newCur)) {
                        queue.offer(newCur);
                        visited.add(newCur);
                    }
                }
            }

            if (foundValid) {
                break;
            }
        }

        return result;
    }

    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
                if (count < 0) {
                    return false;
                }
            }
        }
        return count == 0;
    }
}