前缀和问题集

1371. 每个元音包含偶数次的最长子字符串

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        n = len(s)
        status = 0
        pos = [-1 for _ in range(1 << 5)]
        pos[0] = 0
        ret = 0
        for i in range(n):
            if s[i] == 'a':
                status ^= 1 << 4
            elif s[i] == 'e':
                status ^= 1 << 3
            elif s[i] == 'i':
                status ^= 1 << 2
            elif s[i] == 'o':
                status ^= 1 << 1
            elif s[i] == 'u':
                status ^= 1
            if pos[status] == -1:
                pos[status] = i+1
            else:
                ret = max(ret, i+1-pos[status])
        return ret

这个问题的关键在于利用前缀和来确定子串的状态。这里的前缀和定义为前$i$个字符中，每个元音字符出现的奇偶性，用来代替出现的次数。我们用二进制编码来代替状态的哈希结构，比如前$i$个字符a, e, i, o, u出现的次数的奇偶性分别为奇，奇，偶，偶，偶，则其编码为11000。只要我们知道前$i$个字符的状态和前$j$个字符的状态，我们就可以知道从第$i+1$个字符到第$j$个字符的元音出现次数奇偶性状态，也就是只要前$i$个字符的二进制编码和前$j$个字符的二进制编码相同，我们就可以确定$i+1$到$j$元音出现次数为偶数。原因在于差为偶则被减数和减数奇偶性相同。

难点1：前缀和由出现次数转换为奇偶性

优化点1：二进制编码

优化点2：抛弃哈希记录每个字符的前缀和，反而用编码作为key来记录该前缀和出现的index，将时间复杂度从$O(n^2)$降至$O(n)$

边界点1：pos[0]=0，原因在于非原因字符最早出现的index一定是空字符串