Leetcode 1249. Minimum Remove to Make Valid Parentheses

 Valid Parentheses这个系列如果熟悉的话就知道非法的右括号‘）’是很容易分辨的，可以用栈也可以用简单计数找出。困难的地方在于左括号‘（’是没法在当时判定是否合法的。那么我们就需要记录下所有的左括号位置，当match的时候划掉合法的左括号，最后剩下的就是非法的。

这个题还有个不容易想到的方法，既然右括号很容易辨别合法性，我们可以反转字符串然后用同样的方法判定左括号。这样可以做到O(1)空间复杂度。这里贴上这种算法的代码。

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string s1 = buildString(s, '(',')');
        reverse(s1.begin(), s1.end());
        string s2 = buildString(s1, ')','(');
        reverse(s2.begin(), s2.end());
        return s2;
    }

    string buildString(string s, char open, char close){
        int count=0;
        string res="";
        for(int i=0; i<s.size(); i++){
            if(s[i]==open){
                count++;
            }else if(s[i]==close){
                if(count==0){
                    continue;
                }
                count--;
            }
            res+=s[i];
        }

        return res;
    } 
};