难度: Medium
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = "eleetminicoworoep" 输出：13 解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = "leetcodeisgreat" 输出：5 解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3：
输入：s = "bcbcbc" 输出：6 解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
提示：
1 <= s.length <= 5 x 10^5s 只包含小写英文字母。运行时间: 149 ms
内存: 22.6 MB
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
mp = {j: 1 << i for i, j in enumerate("aeiou")}
st = [0] * (len(s)+1)
n = len(st)
for i, j in enumerate(s):
st[i+1] = (st[i] ^ p) if (p:=mp.get(j)) else st[i]
for i in range(n-1, 0, -1):
for j in range(n - i):
if st[j + i] == st[j]:
return i
return 0
本题的核心思想是使用位掩码来跟踪元音字母的出现次数的奇偶性。每个元音字母对应于位掩码中的一个位，如果该字母出现奇数次，相应的位为1，偶数次则为0。通过XOR操作更新位掩码，从而不需要直接计数。数组`st`用于存储从字符串开头到当前位置的所有字符的位掩码。如果在两个位置`i`和`j`（其中`i < j`）的位掩码相同，这意味着从`i+1`到`j`的子字符串中所有元音字母出现了偶数次。因此，问题转化为寻找最大的`j - i`，其中`st[j] == st[i]`。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
mp = {j: 1 << i for i, j in enumerate('aeiou')} # 创建映射，每个元音对应一个位掩码
st = [0] * (len(s)+1) # 初始化位掩码数组，st[0]为0表示空字符串的位掩码
n = len(st)
for i, j in enumerate(s): # 构建st数组，记录到当前字符为止的位掩码状态
st[i+1] = (st[i] ^ p) if (p:=mp.get(j)) else st[i]
for i in range(n-1, 0, -1): # 从后向前检查每个可能的子字符串长度
for j in range(n - i): # 检查该长度下所有可能的起始位置
if st[j + i] == st[j]: # 如果位掩码相同，返回当前长度
return i
return 0 # 如果没有找到，返回0
位异或操作（XOR）非常适合于跟踪出现次数的奇偶性。在二进制中，XOR操作具有翻转特性：对同一个数值进行两次XOR操作会恢复原值。因此，每次字符出现时，通过对应位进行XOR操作，可以有效地切换该位的状态（从0到1或从1到0），直接反映该字符出现次数的奇偶变化。这种方法既节省了存储空间，又简化了计算过程。
位掩码数组`st`的初始化是将`st[0]`设置为0，表示一个空字符串的位掩码。该初始值表明此时没有任何字符被处理，所有元音字母的出现次数默认为偶数（即0次）。随后，遍历字符串中的每个字符，若该字符是元音，则根据元音字母到位掩码的映射来更新当前位掩码，使用XOR操作反映其出现次数的变化。这种逐步构建保证了数组在每个位置上都正确反映了到该位置为止所有元音字母的出现奇偶性。
当两个位置的位掩码相同，即`st[j] == st[i]`，这表明从字符串的开始到位置`i`和到位置`j`的元音字母出现次数的奇偶性完全相同。因此，从`i+1`到`j`的区间内，每个元音字母的出现次数必然是偶数次，因为其在这段区间内的出现次数变化抵消了（即奇偶性没有改变）。这是因为任何元音字母的奇数次出现都会改变其对应位的状态，而状态未改变说明出现次数为偶数。
对于不在映射`mp`中的非元音字符，它们不会影响元音字母出现次数的奇偶性跟踪。在题解的算法实现中，当遍历到非元音字符时，位掩码不进行更新，即`st[i+1]`直接继承`st[i]`的值。这样处理保证了位掩码数组只记录和更新元音字母的状态，而忽略非元音字符的干扰。