[LeetCode] 301. 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())()"]
")(" -> [""]

Solution: Iterate all characters. When found illegal situations, iterate the current substring and remove the first character which causes the invalid. Recursively call the function with the new string.
For the first time, remove the illegal ')'. Second time, remove illegal '('. Add the valid string to the result when the iterations over.

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> ret = new ArrayList();
        if (s == null) return ret;

        remove(s, 0, 0, ret, '(', ')');
        if (ret.isEmpty()) ret.add("");
        return ret;
    }
    
    public void remove(String s, int last_i, int last_j, List<String> ret, char pos, char neg) {
        int count = 0;
        for (int i = last_i; i < s.length(); i++) {
            if (s.charAt(i) == pos) count++;
            else if (s.charAt(i) == neg) count--;
            
            if (count < 0) {
                for (int j = last_j ;j <= i; j++) {
                    if (s.charAt(j) == neg && (j == 0 || s.charAt(j - 1) != neg)) {
                        remove(s.substring(0, j) + s.substring(j + 1, s.length()), i, j, ret, pos, neg);
                    }
                }
                return;
            }
        }
        
        if (pos == '(') remove(new StringBuilder(s).reverse().toString(), 0, 0, ret, ')', '(');
        else ret.add(new StringBuilder(s).reverse().toString());
    }
}