Leetcode https://leetcode.com/problems/remove-invalid-parentheses/, beating 75% submissions.

leetcode-remove-invalid-parentheses.java

class Solution {
    public List<String> removeInvalidParentheses(
        String s
    ) {
        // Find how many left and right parentheses to remove.
        final int[] parenToRemove = new int[2];
        computeParanToRemove(s, parenToRemove);
        final int l = parenToRemove[0];
        final int r = parenToRemove[1];
        
        final StringBuilder sb = new StringBuilder(s.length());
        
        // Enumerate all the valid mutated string with DFS.
        final List<String> ans = new ArrayList<>();
        dfs(s, 0, l, r, sb, ans);
        
        return ans;
    }
    
    private void dfs(
        String s,
        int start,
        int leftToRemove,
        int rightToRemove,
        StringBuilder sb,
        List<String> ans
    ) {
        // System.out.println(String.format("%-10s, start: %d, i: %d, r: %d", s, start, leftToRemove, rightToRemove));
        
        if (leftToRemove == 0 && rightToRemove == 0) {
            // Validate parentheses
            final int[] parenToRemove = new int[2];
            computeParanToRemove(s, parenToRemove);
            final int l = parenToRemove[0];
            final int r = parenToRemove[1];
            
            if (l == 0 && r == 0) {
                ans.add(s);
            }
        } else {
            final char compareToChar;
            final int dl; // Delta left for the left-to-remove
            final int dr; // Delta right for the right-to-remove
            if (rightToRemove > 0) {
                // Remove right parenthese to make the prefix valid.
                // Our DFS finds the candidate after "start" therefore the
                // valid prefix is so important.
                // Not guarenteeing this order will fail in this case:
                // ")("
                compareToChar = ')';
                dl = 0;
                dr = -1;
            } else {
                // Remove left parenthese.
                compareToChar = '(';
                dl = -1;
                dr = 0;
            }
            
            char last = '#';
            for (int i = start; i < s.length(); ++i) {
                final char c = s.charAt(i);
                if (c == compareToChar && last != compareToChar) {
                    sb.delete(0, sb.length());
                    sb.append(s.substring(0, i));
                    sb.append(s.substring(i + 1));
                    dfs(sb.toString(), i, leftToRemove + dl, rightToRemove + dr, sb, ans);
                }

                // Remember the visited char to avoid duplicates.
                last = c;
            }
        }
    }
    
    private void computeParanToRemove(
        String s,
        int[] parenToRemove
    ) {
        int l = 0;
        int r = 0;
        for (int i = 0; i < s.length(); ++i) {
            final char c = s.charAt(i);
            if (c == '(') {
                ++l;
            } else if (c == ')') {
                if (l == 0) {
                    ++r;
                } else {
                    --l;
                }
            }
        }
        
        parenToRemove[0] = l;
        parenToRemove[1] = r;
    }
}