括号序列

性质：
1、括号序列合法等价于所有前缀和均大于等于0，
2、且总和等于0

设左括号为1，右括号为-1
)()())
表示为 -1,1,-1,1,-1,-1

判断是否合法括号序列

start:当前枚举的这一段的开头
cnt:前缀和

1、cnt<0 => 左指针直接往后移动到当前位置之后的i+1，start = i+1, cnt = 0
注意不能让左指针一个一个右移，因为每个右括号唯一匹配另一半边括号，若此时已经无法匹配
则只要包括它之前的序列值，这种序列永远也无法构成合法的括号序列，所以直接跳过它，到它的下一位开始遍历
2、cnt>0 => 满足第一条性质，右指针继续右移
3、cnt == 0 => 满足两条性质，[start,i]是一段合法的括号序列

• 但这样做只能找出右括号多于左括号的括号序列
• 所以要对称地做一遍找出左括号多于右括号的括号序列

怎么对称做一遍？

1、先把序列翻转reverse
2、再把左右括号相互转换
查看左右括号ASCII， 在C++ ( 为0x28, ) 为0x29,二进制中最后一位不等
所以把左括号异或1就能转化右括号 c ^= 1

Py代码

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res = self.work(s)
        s = s[::-1]
        s2 = ''
        for i in range(len(s)): 
            s2 += chr(ord(s[i])^1)
            # s[i] = chr(ord(s[i])^1) # 左右括号互转 
            # 在python中,字符串是不可变对象,不能通过下标的方式直接赋值修..
            # python左右括号ASCII码为40,41，先转码再转回字符
        # print(s2)
        return max(res, self.work(s2))

    def work(self, s):
        res = 0
        start = 0; cnt = 0
        i = 0
        while i < len(s):
            if s[i] == '(': cnt += 1
            else:
                cnt -= 1
                if cnt < 0:
                    start = i +1
                    cnt = 0
                elif cnt == 0: # 得到合法括号序列，更新最长答案
                    res = max(res, i - start + 1)
            i += 1
        return res