301. Remove Invalid Parentheses

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int leftRemoval = 0;
        int rightRemoval = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftRemoval ++;
            } else if (c == ')') {
                if (leftRemoval != 0) {
                    leftRemoval --;
                } else {
                    rightRemoval ++;
                }
            }
        }
        List<String> res = new ArrayList<>();
        dfsHelper(s, 0, leftRemoval, rightRemoval, res);
        return res;
    }
    
    private void dfsHelper(String s, int index, int leftRemoval, int rightRemoval, List<String> res) {
        // Nothing to remove
        if (leftRemoval == 0 && rightRemoval == 0) {
            if (isValid(s)) {
                res.add(s);
                return;
            }
        }
        for (int i = index; i < s.length(); i++) {
            // We only remove the first parentheses if there are consecutive ones to avoid duplications.
            if (i != index && s.charAt(i) == s.charAt(i - 1)) {
                continue;
            }
            if (leftRemoval > 0 && s.charAt(i) == '(') {
                dfsHelper(s.substring(0, i) + s.substring(i + 1), i, leftRemoval - 1, rightRemoval, res);
            }
            if (rightRemoval > 0 && s.charAt(i) == ')') {
                dfsHelper(s.substring(0, i) + s.substring(i + 1), i, leftRemoval, rightRemoval - 1, res);
            }
        }
    }
    
    private boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count ++;
            }
            if (c == ')') {
                count --;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}