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:

1. '(': stack + 1, ')' : stack - 1, if stack < 0 more ) than (, break;
2. find the ) in prefix to remove, remove the ) with no consecutive ) or the first ) with consecutive )s.
3. pass the new string to continue, note: here the starting stack cnt index will be the last break point, and the starting index of finding the removable ')' is from the last removed ')' position
4. reverse the string to deal with the case when '(' is more than ')'
5. add result to the list

public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<String>();
        helper(ans, s, 0, 0,new char[]{'(',')'});
        return ans;
    }

    public void helper(List<String> ans, String s, int last_i, int last_j, char[] par){
        int stack = 0;
        int i;
        for(i = last_i; i < s.length(); ++i){
            if(s.charAt(i) == par[0]){
                stack++;
            }else if(s.charAt(i) == par[1]){
                stack--;
            }

            if(stack >= 0){
                continue;
            }else{
                break;
            }
        }
        if(stack < 0){
            for(int j = last_j; j <= i; ++j){
                if(s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1])){
                    String curr_s = s.substring(0,j) + s.substring(j+1, s.length());
                    helper(ans, curr_s, i, j, par);
                }
            }
            return;
        }

        String reverse = new StringBuilder(s).reverse().toString();
        if(par[0] == '('){
            helper(ans, reverse, 0, 0, new char[]{')','('});
        }else{
            ans.add(reverse);
        }
    }

Reference:

http://52.20.106.37/remove-invalid-parentheses/