企业官网建设流程全解析

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 ，请你返回满足以下条件的最长子字符串的长度：每个元音字母， 即 '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^5
• s只包含小写英文字母。

该题在本仓库的题解索引中收录于 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.md）：

class 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 0

JavaScript 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 中强调的核心套路：题目出现"连续"关键字，条件反射想到滑动窗口和前缀和。

具体做法：维护一个二维前缀数组pre，pre[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 Code：

class 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 0

Java Code：

class 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（注意此版本前缀数组为n+1长度，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 位状态。五个元音对应的位掩码为：

第二步：为什么用 0 表示偶数、1 表示奇数？

这背后依赖小学数学性质：

• 如果两个数字奇偶性相同，那么相减一定是偶数；
• 如果两个数字奇偶性不同，那么相减一定是奇数。

而我们打算用异或来转移状态。异或的性质是：对两个二进制逐位运算，相同则位 0，不同则位 1。这与上述奇偶性性质高度吻合——"奇偶性相同则差为偶数，不同则差为奇数"。因此用 0 表示偶数、1 表示奇数，可以让"状态与位运算"无缝衔接：

• 遇到元音v时，cur ^= mask[v]，恰好把该元音位的奇偶性翻转（偶数变奇数、奇数变偶数）；
• 遇到辅音时，cur保持不变。

第三步：区间合法性判定

前缀s[0..i]的状态是cur_i，那么子串s[l+1..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 Code：

class 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 res

JavaScript 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$ 长度的输入，这正是本题期待的最优解。

三种解法对比

可以看到一条清晰的优化主线：暴力统计 → 前缀和去重 → 状态压缩 + 异或。这条主线与本仓库 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