题目描述
思路解析动画文字版
记牢一句话:用 5 位掩码记五个元音的奇偶,扫到当前掩码和之前某下标的掩码相等,中间这段就全偶。下面每一帧都在套这个思路。
准备 · 起点状态 00000：开扫之前先看舞台。上面这排是字符串 "leetcode" 的每个字符。右边面板是状态首现表 d,现在只有一行:状态 00000 配下标 -1。00000 表示五个元音此刻都出现偶数次(都是 0 次),这就是空前缀的状态。把它的首现下标定成 -1,代表它出现在整个字符串开头之前,这个哨兵待会儿处理从头就全偶的子串时非常关键。
准备 · 认识 5 位掩码：说清楚掩码怎么读。它是五位,从左到右依次对应 a、e、i、o、u。某一位是 0 表示那个元音到目前为止出现了偶数次,是 1 表示奇数次。比如 01000 就表示只有 e 出现了奇数次,其余四个都是偶数次。扫描过程中,每遇到一个元音,就把它对应的那一位由 0 翻成 1 或者由 1 翻回 0,这正好对应「次数加一,奇偶反转」。
下标 0 · 读 "l"：扫到下标 0 的字符 "l",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00000。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
下标 0 · 命中状态 00000：查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 0 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 0 减 -1 等于 1。比之前记的最长还大,所以把答案刷新成 1,这段就是目前最优的子串。
下标 1 · 读 "e"：扫到下标 1 的字符 "e",它是元音,所以把掩码里 e 那一位翻一下。翻之前是 00000,翻之后变成 01000,意思是 e 的出现次数奇偶性反过来了。其余四位保持不动。
下标 1 · 新状态 01000：查表发现状态 01000 还没出现过,这是第一次见。那就把它记进表里,首现下标设为 1。为什么只在第一次见时记、而且永远不覆盖?因为我们要的是最长子串,同一个状态留着它最早的下标,将来再遇到同状态时,当前下标减这个最早下标才会最大。
下标 2 · 读 "e"：扫到下标 2 的字符 "e",它是元音,所以把掩码里 e 那一位翻一下。翻之前是 01000,翻之后变成 00000,意思是 e 的出现次数奇偶性反过来了。其余四位保持不动。
下标 2 · 命中状态 00000：查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 2 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 2 减 -1 等于 3。比之前记的最长还大,所以把答案刷新成 3,这段就是目前最优的子串。
洞察 · 掩码相等就意味着全偶：在这里停一下,体会为什么掩码相等就等于全偶。下标 1、2 两个 "e" 让 e 这一位先翻成奇、又翻回偶,掩码从 00000 走了一圈又回到 00000。现在它和哨兵下标 -1 那个 00000 相等。两个相等的状态之间,每个元音的奇偶都没变,等价于每个元音都被翻了偶数次,所以中间这段 "lee" 里 e 出现 2 次、其余元音 0 次,确实全偶。这就是整道题的根。
下标 3 · 读 "t"：扫到下标 3 的字符 "t",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00000。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
下标 3 · 命中状态 00000：查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 3 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 3 减 -1 等于 4。比之前记的最长还大,所以把答案刷新成 4,这段就是目前最优的子串。
下标 4 · 读 "c"：扫到下标 4 的字符 "c",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00000。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
下标 4 · 命中状态 00000：查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 4 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 4 减 -1 等于 5。比之前记的最长还大,所以把答案刷新成 5,这段就是目前最优的子串。
下标 5 · 读 "o"：扫到下标 5 的字符 "o",它是元音,所以把掩码里 o 那一位翻一下。翻之前是 00000,翻之后变成 00010,意思是 o 的出现次数奇偶性反过来了。其余四位保持不动。
下标 5 · 新状态 00010：查表发现状态 00010 还没出现过,这是第一次见。那就把它记进表里,首现下标设为 5。为什么只在第一次见时记、而且永远不覆盖?因为我们要的是最长子串,同一个状态留着它最早的下标,将来再遇到同状态时,当前下标减这个最早下标才会最大。
下标 6 · 读 "d"：扫到下标 6 的字符 "d",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00010。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
下标 6 · 命中状态 00010：查表发现状态 00010 不是第一次见,它最早出现在下标 5。这说明从下标 6 到 6 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 6 减 5 等于 1。不过它没有超过当前已经记下的最长 5,所以答案保持不变。注意这里不更新表里的下标,因为要的是最早出现的位置,留着它才能在以后配出更长的段。
下标 7 · 读 "e"：扫到下标 7 的字符 "e",它是元音,所以把掩码里 e 那一位翻一下。翻之前是 00010,翻之后变成 01010,意思是 e 的出现次数奇偶性反过来了。其余四位保持不动。
下标 7 · 新状态 01010：查表发现状态 01010 还没出现过,这是第一次见。那就把它记进表里,首现下标设为 7。为什么只在第一次见时记、而且永远不覆盖?因为我们要的是最长子串,同一个状态留着它最早的下标,将来再遇到同状态时,当前下标减这个最早下标才会最大。
小结 · 全部出现过的状态：扫描结束前看一眼这张表,它一共记下了 4 种不同的奇偶状态,每种都只存了第一次出现的下标。哪怕字符串再长,这张表也最多 32 行,因为五个元音的奇偶组合总共就 32 种。整个算法的省力之处,就是把数元音这件累活,换成了在这张小表里查状态有没有见过。
完成 · 答案 5：整个字符串扫完了。绿色高亮的就是最长的全偶子串 "leetc",下标 0 到 4,长度 5。回放一下关键点:当 i 走到 4 时掩码是 00000,和哨兵下标 -1 相等,于是子串 [0 到 4] 全偶,长度 5,这就是答案。后面下标 5 的 "o" 让 o 变成奇数,状态变了,再也凑不出更长的全偶段。全程只扫一遍,每一步查表都是常数时间。
边界先想清:没有元音时整串都算、两个相同元音翻回偶得整段、单个元音落单时凑不出全偶子串答案是 0。
面试重点:只关心奇偶所以压成 5 位、状态最多 32 种所以空间 O(1)、它和前缀和前缀异或是同一套前缀加表的家族。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findTheLongestSubstring(self, s: str) -> int: d = {0: -1} ans = mask = 0 for i, c in enumerate(s): if c in "aeiou": mask ^= 1 << (ord(c) - ord("a")) if mask in d: j = d[mask] ans = max(ans, i - j) else: d[mask] = i return ans复杂度
- 时间：O(n)，n 是字符串长度。从左到右只扫一遍,每个字符做的事是翻一位、查一次表、更新一下答案,都是常数时间,合计 O(n)
- 空间：O(1)，五个元音只有 2 的 5 次方等于 32 种奇偶状态,表里最多 32 行,是与 n 无关的常数;掩码、答案是几个标量,所以额外空间峰值 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么用 5 位掩码就够,而不用真的去数每个元音几次?
追问空间为什么是 O(1) 而不是 O(n)?表不是可能记很多下标吗?
追问这道题和前缀和、前缀异或那一类是什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
形成两个异或相等数组的三元组数目
LeetCode 1442 · 中等 · 沿着 字典树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题