1249. Minimum Remove to Make Valid Parentheses

跟301. Remove Invalid Parentheses不完全一样
跟921. Minimum Add to Make Parentheses Valid结合起来看
O(n) time

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        s = remove(s, '(', ')'); // 一定要先从后往前删，再从前往后删，因为s要翻转两次
        return remove(s, ')', '(');
    }

    string remove(const string &s, char lp, char rp) {
        string res;
        int cnt = 0;
        for (int n = s.length(), i = n - 1; i >= 0; --i) {
            cnt += s[i] == lp ? -1 : (s[i] == rp);
            if (cnt < 0) { // 说明找到一个无法匹配的『左括号』
                cnt = 0; // 重置
                continue;
            }
            res += s[i];
        }
        return res;
    }
};

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        reverse(begin(s), end(s));
        s = remove(s, ')', '(');
        reverse(begin(s), end(s));
        return remove(s, '(', ')');
    }

    string remove(const string &s, char lp, char rp) {
        string res;
        int cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            cnt += s[i] == rp ? -1 : (s[i] == lp);
            if (cnt < 0) {
                cnt = 0;
                continue;
            }
            res += s[i];
        }
        return res;
    }
};