LC 1371. Find the Longest Substring Containing Vowels in Even Counts

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

这题其实不难，但是似乎有某种思想在里面。这种思想是：

在遍历期间保存每步计算得到的状态
可以根据当前的状态找到我们期望匹配到的状态

然后来分析一下原题：

要求每个字符是偶数个，所以状态就是各种字符的奇偶性，一种32种状态
然后我们期望的状态也是相同的状态，这样相减就能满足每个字符都是偶数个
如果要求每个字符是奇数的话，那么就是取反的状态 (31 - st)

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        n = len(s)
        mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
        inf = 1 << 30
        dp = [inf] * 32
        dp[0] = -1

        res = 0
        ans = 0
        for i in range(n):
            c = s[i]
            v = mapping.get(c)
            if v is not None:
                res ^= (1 << v)
            if dp[res] != inf:
                ans = max(ans, i - dp[res])
            else:
                dp[res] = i
        return ans

和这题很像是的 https://leetcode.com/problems/contiguous-array/

状态st = count(0) - count(1)
我们期望匹配的状态也是st

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        past = {}
        past[0] = -1

        t = 0
        ans = 0
        for i, x in enumerate(nums):
            if x == 1:
                t += 1
            else:
                t -= 1
            if t in past:
                ans = max(ans, i - past[t])
            else:
                past[t] = i
        return ans