1371. 每个元音包含偶数次的最长子字符串前缀和 状态压缩的完整推导LeetCode 题解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南围绕 LeetCode 1371「每个元音包含偶数次的最长子字符串」展开以本仓库 problems/1371.find-the-longest-substring-containing-vowels-in-even-counts.md 的官方题解为主体完整梳理暴力法、前缀和、状态压缩三条递进解法路线并结合仓库中 前缀和专题、位运算专题 与同思路题目 1310. 子数组异或查询 做源码级佐证。读完本文你将掌握如何识别区间奇偶性类问题、如何用异或运算压缩状态、如何从 $O(n^3)$ 暴力一路优化到 $O(n)$ 线性扫描。题目描述给你一个字符串 s 请你返回满足以下条件的最长子字符串的长度每个元音字母 即 aeiou 在子字符串中都恰好出现了偶数次。示例 1输入s eleetminicoworoep 输出13 解释最长子字符串是 leetminicowor 它包含 eio 各 2 个以及 0 个 au 。示例 2输入s leetcodeisgreat 输出5 解释最长子字符串是 leetc 其中包含 2 个 e 。示例 3输入s bcbcbc 输出6 解释这个示例中字符串 bcbcbc 本身就是最长的因为所有的元音 aeiou 都出现了 0 次。提示1 s.length 5 x 10^5s只包含小写英文字母。该题在本仓库的题解索引中收录于 README.md 与 collections/medium.md 的中等难度列表是前缀和 状态压缩这一类题型的经典代表。前置知识前缀和仓库 thinkings/prefix.md 详细讲解了前缀和的母题与套路——数列的前 n 项的和pre[i] pre[i-1] nums[i]。前缀和适合处理连续限制下的区间查询优化。状态压缩当状态只有有限几种例如奇偶两种时可以用二进制位来紧凑表示配合位运算异或快速转移。仓库 位运算专题 汇总了这类位运算技巧。思路起点为什么滑动窗口不行拿到题目第一反应通常是可变滑动窗口扩张、收缩窗口维护某个指标。但这里被很快否定——题目要求的是元音出现次数的奇偶性而不是元音出现最多的子串之类的可单调维护指标。滑动窗口的核心前提是窗口收缩时指标可逆地退化而奇偶性在窗口左端收缩时并不能简单地还原你无法知道被移出的字符是否曾经把某个计数从偶数翻成奇数因此滑动窗口无法优雅求解。排除了滑动窗口先从最朴素的暴力法开始。解法一暴力法 剪枝思路暴力法的思路朴素直观双层循环枚举所有子串对每一个子串统计元音个数如果所有元音个数都是偶数则更新答案最后返回满足条件的最大子串长度。这里有一个小 trick枚举子串时从最长开始这样一旦找到满足条件的子串直接返回early return无需维护最大值。这样既减少了代码量又提升了效率——最坏情况虽仍是 $O(n^3)$但平均情况下能提前结束。代码Python3 Code来自 problems/1371.find-the-longest-substring-containing-vowels-in-even-counts.mdclass Solution: def findTheLongestSubstring(self, s: str) - int: for i in range(len(s), 0, -1): for j in range(len(s) - i 1): sub s[j:j i] has_odd_vowel False for vowel in [a, e, i, o, u]: if sub.count(vowel) % 2 ! 0: has_odd_vowel True break if not has_odd_vowel: return i return 0JavaScript Code来自英文版题解 problems/1371.find-the-longest-substring-containing-vowels-in-even-counts.en.md/** * param {string} s * return {number} */ var findTheLongestSubstring function (s) { const vowels [a, e, i, o, u] const hasEvenVowels s !vowels.some(v (s.match(new RegExp(v, g))||[]).length % 2 ! 0) for (let subStrLen s.length; subStrLen 0; subStrLen--) { let remove s.length - subStrLen 1 for (let start 0; start remove; start) { let subStr s.slice(start, start subStrLen) if (hasEvenVowels(subStr)) { return subStrLen } } } };复杂度分析时间复杂度$O(n^3)$。双层循环找出所有子串的复杂度是 $O(n^2)$统计元音个数复杂度也是 $O(n)$因此整体为 $O(n^3)$。空间复杂度$O(1)$。面对5 x 10^5的数据范围$O(n^3)$ 显然不可行必须优化。解法二前缀和 剪枝思路观察暴力法瓶颈在于对每个子串重复统计元音个数——相邻子串之间存在大量重复计算。对于连续区间的统计问题很自然地想到用前缀和来优化这正是 thinkings/prefix.md 中强调的核心套路题目出现连续关键字条件反射想到滑动窗口和前缀和。具体做法维护一个二维前缀数组prepre[i][j]表示字符串前缀s[0..i]中第j个元音a,e,i,o,u依次对应下标0,1,2,3,4出现的总次数。那么子串s[l..r]中元音j的出现次数可以用两次前缀相减得到配合边界修正即可在 $O(1)$ 时间内判断一个子串是否合法。这种空间换时间策略把时间复杂度降到 $O(n^2)$空间复杂度上升到 $O(n)$——在数据规模可控时通常是值得的取舍。代码Python3 Codeclass Solution: i_mapper { a: 0, e: 1, i: 2, o: 3, u: 4 } def check(self, s, pre, l, r): for i in range(5): if s[l] in self.i_mapper and i self.i_mapper[s[l]]: cnt 1 else: cnt 0 if (pre[r][i] - pre[l][i] cnt) % 2 ! 0: return False return True def findTheLongestSubstring(self, s: str) - int: n len(s) pre [[0] * 5 for _ in range(n)] # pre for i in range(n): for j in range(5): if s[i] in self.i_mapper and self.i_mapper[s[i]] j: pre[i][j] pre[i - 1][j] 1 else: pre[i][j] pre[i - 1][j] for i in range(n - 1, -1, -1): for j in range(n - i): if self.check(s, pre, j, i j): return i 1 return 0Java Codeclass Solution { public int findTheLongestSubstring(String s) { int len s.length(); if (len 0) return 0; int[][] preSum new int[len][5]; int start getIndex(s.charAt(0)); if (start ! -1) preSum[0][start]; // preSum for (int i 1; i len; i) { int idx getIndex(s.charAt(i)); for (int j 0; j 5; j) { if (idx j) preSum[i][j] preSum[i - 1][j] 1; else preSum[i][j] preSum[i - 1][j]; } } for (int i len - 1; i 0; i--) { for (int j 0; j len - i; j) { if (checkValid(preSum, s, j, i j)) return i 1; } } return 0; } public boolean checkValid(int[][] preSum, String s, int left, int right) { int idx getIndex(s.charAt(left)); for (int i 0; i 5; i) if (((preSum[right][i] - preSum[left][i] (idx i ? 1 : 0)) 1) 1) return false; return true; } public int getIndex(char ch) { if (ch a) return 0; else if (ch e) return 1; else if (ch i) return 2; else if (ch o) return 3; else if (ch u) return 4; else return -1; } }JavaScript Code注意此版本前缀数组为n1长度prefixes[i]表示前i个字符的统计区间查询用prefixes[r 1] - prefixes[l 1]与 Python/Java 版的边界处理略有不同但思路一致/** * param {string} s * return {number} */ var findTheLongestSubstring function (s) { const prefixes Array(s.length 1) .fill(0) .map((el) Array(5).fill(0)); const vowels { a: 0, e: 1, i: 2, o: 3, u: 4, }; for (let i 1; i s.length 1; i) { const letter s[i - 1]; for (let j 0; j 5; j) { prefixes[i][j] prefixes[i - 1][j]; } if (letter in vowels) { prefixes[i][vowels[letter]] prefixes[i - 1][vowels[letter]] 1; } } const check (s, prefixes, l, r) { for (let i 0; i 5; i) { const count s[l] in vowels vowels[s[l]] i; if ((prefixes[r 1][i] - prefixes[l 1][i] count) % 2 ! 0) { return false; } } return true; }; for (let r s.length - 1; r 0; r--) { for (let l 0; l s.length - r; l) { if (check(s, prefixes, l, l r)) { return r 1; } } } return 0; };复杂度分析时间复杂度$O(n^2)$。空间复杂度$O(n)$。解法三前缀和 状态压缩最优解思路前面前缀和思路用空间换时间把复杂度压到了 $O(n^2)$但仍是平方级。还能继续优化吗关键在于我们只关心奇偶性并不关心每个元音具体出现的次数。因此可以用是奇数 / 是偶数两个状态来表示而只有两个状态时最适合用位运算。第一步用 5 位二进制压缩状态使用 5 位二进制表示以i结尾的前缀中各个元音出现次数的奇偶性0 表示偶数1 表示奇数最低位表示a依次向上是e、i、o、u。例如二进制10110表示包含偶数个a和o奇数个e、i、u。用变量cur表示这个 5 位状态。五个元音对应的位掩码为元音位掩码a1 (00001)e2 (00010)i4 (00100)o8 (01000)u16 (10000)第二步为什么用 0 表示偶数、1 表示奇数这背后依赖小学数学性质如果两个数字奇偶性相同那么相减一定是偶数如果两个数字奇偶性不同那么相减一定是奇数。而我们打算用异或来转移状态。异或的性质是对两个二进制逐位运算相同则位 0不同则位 1。这与上述奇偶性性质高度吻合——奇偶性相同则差为偶数不同则差为奇数。因此用 0 表示偶数、1 表示奇数可以让状态与位运算无缝衔接遇到元音v时cur ^ mask[v]恰好把该元音位的奇偶性翻转偶数变奇数、奇数变偶数遇到辅音时cur保持不变。第三步区间合法性判定前缀s[0..i]的状态是cur_i那么子串s[l1..r]的元音奇偶性状态就是cur_l ^ cur_r这与 1310. 子数组异或查询 中前缀异或相减抵消重复项的性质完全同源——x ^ y ^ x y。若cur_l ^ cur_r 0说明该子串所有元音都出现偶数次即合法。等价地两个前缀状态相同cur_l cur_r时它们之间的子串必然合法。第四步哈希表记录最早出现位置于是问题转化为扫描过程中用哈希表seen记录每个cur状态第一次出现的位置当同一个状态再次出现时i - seen[cur]就是一个合法子串长度不断取最大值即可。初始时seen {0: -1}表示空前缀位置 -1的状态为 0所有元音出现 0 次均为偶数。代码Python3 Codeclass Solution: def findTheLongestSubstring(self, s: str) - int: mapper { a: 1, e: 2, i: 4, o: 8, u: 16 } seen {0: -1} res cur 0 for i in range(len(s)): if s[i] in mapper: cur ^ mapper.get(s[i]) # 全部奇偶性都相同相减一定都是偶数 if cur in seen: res max(res, i - seen.get(cur)) else: seen[cur] i return resJavaScript Code/** * param {string} s * return {number} */ var findTheLongestSubstring function (s) { const mapper { a: 1, e: 2, i: 4, o: 8, u: 16, }; let max 0, cur 0; const seen { 0: -1 }; for (let i 0; i s.length; i) { if (s[i] in mapper) { cur ^ mapper[s[i]]; } if (cur in seen) { max Math.max(max, i - seen[cur]); } else { seen[cur] i; } } return max; };复杂度分析时间复杂度$O(n)$单次线性扫描。空间复杂度$O(n)$保守估计实际上cur只有 5 位最多 $2^5 32$ 种不同状态因此seen最多存放 32 个键空间可视为 $O(1)$ 常数级别。单遍扫描即可解决 $5 \times 10^5$ 长度的输入这正是本题期待的最优解。三种解法对比解法核心思想时间复杂度空间复杂度适用性暴力法 剪枝枚举所有子串 统计元音 从长到短提前返回$O(n^3)$$O(1)$仅作思路铺垫前缀和 剪枝前缀数组消除重复统计$O(1)$ 判区间$O(n^2)$$O(n)$数据规模较小时可用前缀和 状态压缩5 位二进制压奇偶 异或转移 哈希记录首现位置$O(n)$$O(n)$实际常数大规模输入的最终方案可以看到一条清晰的优化主线暴力统计 → 前缀和去重 → 状态压缩 异或。这条主线与本仓库 thinkings/prefix.md 末尾的总结完全呼应——先写出暴力解然后找暴力解的瓶颈根据瓶颈就知道该用什么数据结构和算法去优化。关键点解析前缀和连续区间统计问题的通用优化手段本仓库 前缀和专题 中的母题 0 给出了pre[i] pre[i-1] nums[i]的标准构造方式本题将和推广为每个元音出现次数与奇偶状态。状态压缩只关心奇偶性时用 5 位二进制 异或操作压缩并转移状态配合x ^ y ^ x y的性质完成区间判定——这与 1310. 子数组异或查询 中前缀异或的推导如出一辙属于同一套路在不同题目上的复用。哈希表 首现位置状态相同即区间合法用seen记录每个状态最早出现的位置一趟扫描求出全局最长。延伸与练习状态压缩思路是前缀和 哈希类问题的典型应用掌握后可尝试本仓库中同类前缀问题560. 和为 K 的子数组哈希 前缀和、1310. 子数组异或查询前缀异或、1186. 删除一次得到子数组最大和。位运算相关通用技巧可进一步阅读本仓库 位运算专题前缀和的系统套路见 前缀和专题其中也将本题列为推荐练习。总结本题的价值不在于背下答案而在于完整展示了从 $O(n^3)$ 暴力到 $O(n)$ 线性解的三级跳识别连续 区间统计特征 → 引入前缀和消除重复计算 → 抓住只关心奇偶的性质用状态压缩 异或降维。这三级跳所依赖的前缀和与位运算正是本仓库 thinkings/prefix.md 与 thinkings/bit.md 两个专题反复强调的核心武器。刷题时若能先写暴力、再找瓶颈、最后套用数据结构与算法优化即可稳定产出这类高效解法。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考