class Solution {
public:
    int longestValidParentheses(string s) {
        //括号序列的两个性质：1、每一个左括号对应的右括号是确定的； 2、如果把左括号视为1，右括号视为-1，括号序列合法等价于所有的前缀和>=0， 并且总和== 0；
        //根据性质2，如果出现了某一个前缀和<0的情况，则说明多出来了一个右括号，再根据性质1，这个多出来的右括号是不可能在前面找到与之匹配的左括号的，所以所有枚举走过的一段都是不合法的，直接跳到下一个重新枚举即可
        //枚举satrt, 计算往右走的前缀和cnt: 如果走到位置i，cnt < 0, 则将start = i+1， cnt = 0； 如果cnt > 0, 则继续往后走i；如果cnt=0， 则说明[start,i]是一段合法的括号序列。这样做可以做出所有右括号数>=左括号数的情况，为了处理左括号数>=右括号数的情况，需要反过来再做一遍start
        int res = work(s);  //正着做一遍
        reverse(s.begin(), s.end());  //翻转字符串
        //翻转字符串的时候必须把左右括号互换，因为只是要纯粹地倒着做一遍
        //左括号的ASC码为0x28，右括号为0x29，所以只有最后一位差了1，直接异或处理一下即可
        for(auto& c: s) c ^= 1;
        return max(res, work(s));
    }

    int work(string s){
        int res = 0;
        for(int i = 0, start = 0, cnt = 0; i < s.size(); i++){
            if(s[i] == '(') cnt++;
            else{
                cnt --;
                if(cnt < 0) start = i+1, cnt = 0;
                else if(!cnt) res = max(res, i-start+1);
            }
        }
        return res;
    }
};