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 ).

RemoveInvalidParentheses.java

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

private static void backtrack(List<String> list, String s, int iStart, int jStart, char[] par) {
    int stack = 0;
    for(int i = iStart; i < s.length(); i++) {
        if(s.charAt(i) == par[0]) stack++;
        else if(s.charAt(i) == par[1]) stack--;

        if(stack >= 0) continue; // valid string s 
        else {
            for(int j = jStart; j <= i; j++)
                if(s.charAt(j) == par[1] && (j == jStart || s.charAt(j-1) != s.charAt(j)))
                backtrack(list, s.substring(0, j) + s.substring(j+1), i, j, par);
            return; // because invalid string s             
        }            
    }

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