1371. Find the Longest Substring Containing Vowels in Even Counts

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

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

然后来分析一下原题:

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/

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