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

Tips:

用maxCount来代表左括号的个数， count来代表单独左括号的个数。max代表总的有效括号的个数。

所以，如果碰到左括号，则先加进去，maxCount + 1， Count + 1， 循环出来后删掉这个左括号，再来。

碰到右括号，则count - 1， maxCount不变。循环出来后同样恢复原状，再来。

Code:

public class Solution {
    int max = 0;
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        helper(result, s, new StringBuilder(), 0, 0);
        if (result.size() == 0) {
            result.add("");
        }
        return result;
    }
    private void helper(List<String> result, String s, StringBuilder current, int maxCount, int count) {
        if (s.length() == 0) {
            if (count == 0 && current.length() != 0) {
                if (maxCount > max) {
                    max = maxCount;
                }
                if (maxCount == max && !result.contains(current.toString())) {
                    result.add(current.toString());
                }
            }
            return;
        }
        if (s.charAt(0) == '(') {
            String temp = current.toString();
            current.append("(");
            helper(result, s.substring(1), current, maxCount + 1, count + 1);
            current = new StringBuilder(temp);
            helper(result, s.substring(1), current, maxCount, count);
        }
        else if (s.charAt(0) == ')'){
            if (count > 0) {
                String temp = current.toString();
                current.append(')');
                helper(result, s.substring(1), current, maxCount, count - 1);
                current = new StringBuilder(temp);
            }
            helper(result, s.substring(1), current, maxCount, count);
        }
        else {
            current.append(s.charAt(0));
            helper(result, s.substring(1), current, maxCount, count);
        }
    }
}