fb

面经题，作为valid parentheses的follow up. 其实很简单，用两个count来计数左括号和右括号. 首先从左往右遍历一次，去掉所有多余的右括号。怎么去的呢？每遇见一个左括号就left++并且append到sb后面，而只有当left>right且遇到右括号的时候，这样的右括号才合法，才能加到stringbuilder sb里面。画一画图就很intuitive了，(()比如这种情况遇到的这个右括号就是合法的，left > right, 说明早就有左括号在等着被匹配了，没毛病。如果不满足条件，就不right++也不加到sb后面，遇到非括号成分，直接加到sb后面。这样从左到右走一遍，多余的右括号都会被去掉。比如()))会得到sb="()"，(()()))会变成(()())但像是(((()这样的就并没有变为合法的，所以我们还要从右往左扫一遍去掉多余的左括号。 记住从右往左扫的时候第一次得到的sb就是我们的原始 string了，然后新建sb来进行合法化，方法类似。

`/*
Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible.
You cannot add anything to the string.
Examples:
balance("()") -> "()"
balance(")(") -> ""
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())". 
balance(")(())(") != "()()"
*/
// only need one of the result?
// O(n) time; if consider the space that sb uses, O(n) space

public String balancedParentheses(String s){
    StringBuilder sb = new StringBuilder();
    //left, right is the count of left and right parentheses, not two pointers here.
    int left = 0;
    int right = 0;
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (c == '('){
            left++;
            sb.append(c);
        } else if (c == ')' && left > right){
            right++;
            sb.append(c);
        } else if (c != ')'){
            sb.append(c);
        }
    }
    String str = sb.toString();
    sb = new StringBuilder();
    left = 0;
    right = 0;
    for (int i = str.length() - 1; i >= 0; i--){
        char c = str.charAt(i);
        if (c == ')'){
            right++;
            sb.append(c);
        } else if (c == '(' && right > left){
            left++;
            sb.append(c);
        } else if (c != '('){
            sb.append(c);
        }
    }
    return sb.reverse().toString();
}