前缀和与状态压缩：解决LeetCode元音偶数次子串问题的O(n)算法

发布时间：2026/7/12 4:31:10

1. 项目概述从“暴力枚举”到“状态压缩”的思维跃迁最近在刷力扣LeetCode第1371题“每个元音包含偶数次的最长子字符串”时我遇到了一个典型的“看起来简单做起来烧脑”的字符串问题。题目要求我们找到一个最长的连续子字符串使得其中每个元音字母a,e,i,o,u出现的次数都是偶数次。乍一看这不就是遍历所有子串然后统计元音频率检查是否全为偶数吗但稍微一算字符串长度n最大可达5 * 10^5子串数量是O(n^2)级别的直接暴力枚举必然超时。这道题的核心魅力就在于它巧妙地引导我们从最朴素的“前缀和”思想出发最终走向“状态压缩”这一精妙的解法完美地将时间复杂度从O(n^2)降到了O(n)。这不仅是算法能力的考验更是对问题抽象和建模思维的一次绝佳训练。无论你是正在准备C面试还是希望深入理解前缀和与状态压缩的应用场景这道题都值得反复咀嚼。2. 核心思路拆解为什么是前缀和与状态压缩2.1 问题重述与暴力法的局限给定一个字符串s我们需要找到最长的连续子串s[i:j]使得在这个子串中五个元音字母a, e, i, o, u的出现次数均为偶数包括0次。最直接的思路是暴力枚举所有可能的子串起点i和终点j0 i j n然后遍历子串s[i:j]统计五个元音的频率最后检查是否全为偶数。这个过程的时间复杂度是O(n^3)枚举子串O(n^2)统计频率O(n)即使优化统计过程也至少是O(n^2)。对于n500000的数据规模这是完全不可接受的。我们需要一个能将复杂度降至O(n)或O(n log n)的算法。2.2 前缀和思想的引入前缀和是处理“子数组子串求和类”问题的利器。其核心思想是预处理一个前缀和数组preSum其中preSum[i]表示原数组前i个元素的和。那么子数组[i, j]的和就可以通过preSum[j1] - preSum[i]在O(1)时间内得到。如何将这个概念应用到我们的问题上我们关心的不是数字的和而是五个元音字母出现次数的“奇偶性”。我们可以定义对于字符串的每一个位置pos0 pos n维护一个长度为5的数组count记录从字符串开头到pos位置包含为止每个元音字母出现的次数。那么对于任意子串s[i:j]其中元音字母vowel的出现次数就等于count[j][vowel] - count[i-1][vowel]当i0时i-1视为-1其计数为0。我们希望这个差值即子串内的计数是偶数。2.3 奇偶性的关键洞察与状态压缩这里有一个至关重要的数学洞察一个数是偶数当且仅当它除以2的余数为0。对于我们的问题我们并不关心元音出现的具体次数只关心其奇偶性即次数模2的结果。设prefix_parity[pos][vowel]表示从开头到pos位置元音vowel出现次数的奇偶性0表示偶数次1表示奇数次。对于子串s[i:j]元音vowel在子串中出现次数的奇偶性可以通过prefix_parity[j][vowel] ^ prefix_parity[i-1][vowel]异或运算得到。为什么因为异或运算相当于模2加法。prefix_parity[j]是起点到j的奇偶性prefix_parity[i-1]是起点到i-1的奇偶性两者异或的结果正好抵消了前i-1个字符的影响只剩下i到j这段子串的影响。我们希望对于所有5个元音这个异或结果都为0即偶数次。这导出了一个更强大的结论子串s[i:j]满足条件的充要条件是prefix_parity[j]与prefix_parity[i-1]完全相同。因为只有当两个状态完全相同时它们的异或结果才会对每一个元音都是0。于是问题被转化了我们遍历字符串计算每个位置pos的奇偶性状态state一个描述5个元音奇偶性的数组。我们需要找到两个位置i-1和j使得它们的state完全相同并且j - (i-1)尽可能大。注意i-1可以取-1即开始之前其状态为(0,0,0,0,0)所有元音出现0次偶数次。现在我们有了一个由n1个状态包括pos-1的状态组成的序列。问题变成了在这个序列中找到两个相同的状态使得它们的下标差最大。这可以用哈希表在C中是unordered_map在O(n)时间内解决第一次遇到某个状态时记录其最早出现的位置再次遇到时用当前位置减去最早位置更新最大长度。2.4 状态压缩从数组到整数state是一个包含5个二进制位0或1的数组。在计算机中这样的结构可以用一个5位的二进制数来完美表示。例如我们可以约定第0位最低位代表u的奇偶性第1位代表o的奇偶性第2位代表i的奇偶性第3位代表e的奇偶性第4位最高位代表a的奇偶性这样状态(a_parity, e_parity, i_parity, o_parity, u_parity)就可以压缩成一个范围在0到31(2^5 - 1) 之间的整数。例如全偶状态(0,0,0,0,0)对应整数0只有a出现奇数次的状态(1,0,0,0,0)对应整数16二进制10000。这种操作就是状态压缩。它的好处是存储高效一个整数替代了一个小数组。比较快速整数比较和哈希作为unordered_map的键比比较数组快得多。更新方便当遇到一个元音字母时我们只需要用异或运算 (^) 翻转对应的位即可。至此完整的算法逻辑浮出水面初始化一个哈希表pos_map记录每个状态第一次出现的位置。将状态0全偶的位置初始化为-1对应开始前的位置。初始化当前状态state 0。遍历字符串s的每个字符ch及其下标i如果ch是元音找到其对应的位掩码mask执行state ^ mask异或翻转该位。检查当前state是否在pos_map中存在如果不存在将(state, i)存入pos_map记录其第一次出现的位置。如果存在设其第一次出现的位置为first_pos则子串s[first_pos1 : i]是一个满足条件的子串长度为i - first_pos。用此长度更新答案max_len。遍历结束后max_len即为答案。这个算法只遍历字符串一次每次更新状态和查询哈希表都是O(1)操作因此总时间复杂度为O(n)空间复杂度为O(32)因为状态只有32种可能完美符合要求。3. 核心细节解析与实操要点3.1 状态定义与位映射的约定状态压缩的核心在于建立字符到二进制位的映射关系。这个映射可以是任意的但必须在整个程序中保持一致。一个清晰且不易出错的约定至关重要。我个人的习惯是按照字母顺序的逆序或正序来映射这样在调试时更容易从整数值反推状态。例如按a, e, i, o, u的顺序从高到低分配比特位// 位掩码定义 const int MASK_A 1 4; // 16, 二进制 10000 const int MASK_E 1 3; // 8, 二进制 01000 const int MASK_I 1 2; // 4, 二进制 00100 const int MASK_O 1 1; // 2, 二进制 00010 const int MASK_U 1 0; // 1, 二进制 00001或者你也可以用一个哈希表来动态映射unordered_mapchar, int vowelMask { {a, 1 4}, {e, 1 3}, {i, 1 2}, {o, 1 1}, {u, 1 0} };后一种方法在遇到元音时直接查表代码更清晰但会有微小的查找开销。在性能关键的场景下使用switch-case或if-else判断字符并硬编码掩码是更优的选择。注意务必确保只对元音字母进行状态翻转。非元音字符不影响状态直接跳过即可。这是初学者常犯的错误之一误将非元音字符也纳入考虑导致状态计算错误。3.2 哈希表初始化的陷阱哈希表pos_map用于存储每个状态第一次出现的位置。这里有一个关键初始化步骤必须将状态0所有元音均出现偶数次即全0状态的“位置”初始化为-1。为什么是-1这对应于整个字符串开始之前的虚拟位置。当我们遍历到某个位置i且当前状态恰好为0时这意味着从字符串开头到i的这个子串即s[0:i]本身就已经满足条件。此时满足条件的子串长度应为i - (-1) i 1。如果不初始化-1当第一个使状态归零的位置出现时我们在哈希表中找不到状态0就会错过这个从开头开始的合法子串。初始化方法unordered_mapint, int pos_map; // key: state, value: first_index pos_map[0] -1; // 虚拟的起始位置状态为全偶3.3 状态更新的逻辑异或运算状态更新是算法的动力源。当我们遇到一个元音字母时需要翻转toggle该元音对应的奇偶性。偶数次遇到变成奇数次奇数次遇到变回偶数次。这个“翻转”操作正是异或^运算的典型应用。假设当前状态state 10二进制01010假设表示e和o是奇数其他是偶数。此时遇到元音e其掩码MASK_E 8二进制01000。执行state ^ MASK_Estate: 01010 MASK_E: 01000 (异或运算) 结果: 00010e对应的位从1变成了0奇变偶其他位不变。这完美地模拟了“遇到一次奇偶性改变”的逻辑。实操心得在代码中务必使用^运算符进行原地更新。确保你的掩码定义正确并且只对元音字符进行此操作。在循环中可以这样写int state 0; for (int i 0; i s.length(); i) { char ch s[i]; switch(ch) { case a: state ^ MASK_A; break; case e: state ^ MASK_E; break; case i: state ^ MASK_I; break; case o: state ^ MASK_O; break; case u: state ^ MASK_U; break; default: break; // 非元音什么都不做 } // ... 后续查找和更新哈希表的逻辑 }switch-case在C中通常比unordered_mapchar, int查找更快尤其是在这种分支少且固定的情况下。3.4 长度计算与答案更新在遍历的每个位置i更新完状态后我们查询哈希表如果state不在pos_map中说明这个状态是第一次出现。我们记录下它的位置i。这里记录的是第一次出现的位置目的是为了后续找到尽可能长的子串因为起点越早长度越长。如果state已在pos_map中设其第一次出现的位置为first_pos。那么子串s[first_pos 1, i]注意是左闭右闭区间一定满足条件。因为从first_pos的状态到i的状态没有变化意味着中间这段子串的净效果是让所有元音的奇偶性保持不变即都变化了偶数次或零次。子串长度len i - first_pos。用这个len去更新全局最大长度max_len。这里first_pos 1是子串的起始索引。因为first_pos位置的状态与i位置的状态相同这意味着从first_pos1到i这段区间内所有元音的变化次数净值为偶数。4. 完整C代码实现与逐行解析理解了所有原理和细节后我们来看完整的C实现。我将提供两个版本一个清晰易懂的版本和一个高度优化、适合面试手写的版本。4.1 清晰注释版#include string #include unordered_map #include algorithm using namespace std; class Solution { public: int findTheLongestSubstring(string s) { // 1. 定义元音字母的位掩码。顺序a, e, i, o, u 对应位4到位0。 const int MASK_A 1 4; // 16 const int MASK_E 1 3; // 8 const int MASK_I 1 2; // 4 const int MASK_O 1 1; // 2 const int MASK_U 1 0; // 1 // 2. 哈希表记录每个状态第一次出现的位置。 // key: 压缩后的状态整数 (0~31) // value: 该状态第一次出现的下标 unordered_mapint, int firstPos; // 3. 初始化全偶状态(0)在虚拟位置-1出现。 // 这代表了字符串开始之前的状态。 firstPos[0] -1; int state 0; // 当前奇偶性状态初始为全0全偶 int maxLen 0; // 记录找到的最长子串长度 // 4. 遍历字符串的每一个字符 for (int i 0; i s.size(); i) { char ch s[i]; // 根据当前字符更新状态只处理元音 switch (ch) { case a: state ^ MASK_A; break; // 翻转a的奇偶位 case e: state ^ MASK_E; break; // 翻转e的奇偶位 case i: state ^ MASK_I; break; // 翻转i的奇偶位 case o: state ^ MASK_O; break; // 翻转o的奇偶位 case u: state ^ MASK_U; break; // 翻转u的奇偶位 default: break; // 非元音字符状态保持不变 } // 5. 检查当前状态是否曾经出现过 if (firstPos.find(state) ! firstPos.end()) { // 如果出现过计算当前下标i与第一次出现位置之间的差值 // 这个差值就是以 firstPos[state]1 为起点i为终点的子串长度 int currentLen i - firstPos[state]; // 更新最大长度 maxLen max(maxLen, currentLen); } else { // 如果没出现过记录当前状态第一次出现的位置就是i firstPos[state] i; } } // 6. 返回找到的最大长度 return maxLen; } };4.2 精简高效版面试推荐这个版本去掉了一些注释使用了更紧凑的写法但逻辑完全一致。class Solution { public: int findTheLongestSubstring(string s) { // 数组替代哈希表因为状态只有32种可能用数组访问更快。 // 初始化为-2表示该状态尚未出现。 vectorint firstPos(32, -2); firstPos[0] -1; // 状态0在位置-1出现 int state 0; int maxLen 0; // 预定义的掩码方便switch内使用 const int mask[26] { 14, 0,0,0, 13,0,0,0,12,0,0,0,0,0,11,0,0,0,0,0,10,0,0,0,0,0 // a的索引0对应16 e的索引4对应8 i的索引8对应4 o的索引14对应2 u的索引20对应1 }; for (int i 0; i s.size(); i) { char ch s[i]; // 只处理元音非元音字符在mask中对应0异或操作不影响状态。 state ^ mask[ch - a]; if (firstPos[state] ! -2) { // 状态已出现过计算长度 maxLen max(maxLen, i - firstPos[state]); } else { // 状态第一次出现记录位置 firstPos[state] i; } } return maxLen; } };精简版解析数组替代哈希表因为状态只有32种0~31使用定长数组vectorint(32, -2)比unordered_map更快。-2作为一个特殊值表示该状态未出现过。掩码表我们创建了一个长度为26的数组mask对应26个小写字母。元音字母在对应索引处设置了正确的位掩码非元音字母处为0。这样更新状态只需一行state ^ mask[ch - a];。对于非元音与0异或不改变state逻辑正确且简洁。逻辑不变核心的“状态首次出现则记录再次出现则计算长度”的逻辑与清晰版完全一致。性能对比提示在力扣的评测环境中数组版本通常比哈希表版本快上几毫秒因为避免了哈希计算的开销。在面试中如果你能主动提到“由于状态空间只有32可以用数组替代哈希表进行常数级优化”会是一个很好的加分项。5. 算法正确性证明与思维延伸5.1 为什么这个算法是正确的我们可以从数学上严格证明算法的正确性。定义设P(k)为字符串s的前k个字符s[0..k-1]中五个元音奇偶性组成的状态一个5位二进制数。引理子串s[i..j]满足“所有元音出现偶数次”的充要条件是P(j1) P(i)。证明必要性如果s[i..j]满足条件那么对于每个元音它在子串中出现的次数是偶数。P(j1)表示从开头到j的奇偶性P(i)表示从开头到i-1的奇偶性。由于从i到j的增量即子串内的次数是偶数在模2加法异或下偶数增量意味着P(j1) ^ P(i) 0所以P(j1) P(i)。充分性如果P(j1) P(i)那么P(j1) ^ P(i) 0。这意味着对于每个元音从位置i到位置j的出现次数的奇偶性变化为0即变化了偶数次。因此子串s[i..j]满足条件。我们的算法遍历所有位置j代码中的i并查找与当前状态P(j1)相同的、最早出现的状态P(i)。j - i就是满足条件的子串长度。通过维护每个状态最早出现的位置我们一定能找到以j为结尾的最长合法子串。对所有j取最大值就得到了全局最长子串。初始化P(0) 0且其位置为-1保证了从头开始的子串也能被考虑到。5.2 思维延伸还能解决什么问题这种“前缀和状态压缩哈希表”的范式是解决一大类“子数组子串计数问题”的通用框架。其核心特征是可加性/可减性子区间的某种统计量可以由两个前缀的统计量推导出来通常是相减或异或。状态空间小前缀统计量的可能取值是有限的、可枚举的。特别是当统计量是某种“模意义下的值”如奇偶性、模k余数或“集合状态”如出现/未出现时状态压缩非常有效。类似问题举例和为K的子数组前缀和直接相减等于K。状态是前缀和的值但值域可能很大通常用哈希表记录前缀和出现的次数。每个元素最多出现两次的最长子数组可以将每个数字的状态压缩为两位00未出现01出现一次10出现两次11无效。状态数最多4^n但n很大时不可行需要其他技巧。但这展示了状态压缩的思想。包含所有元音字母至少一次的最长子字符串状态可以压缩为5位但表示的是“是否出现”而不是“奇偶”。我们需要找状态为11111(二进制31) 的子串或者更复杂地找两个前缀状态使得它们的异或结果包含所有位为1即出现了所有元音。这需要调整判断条件。乘积为K的倍数的子数组记录前缀乘积模K的余数。掌握这个范式你就能举一反三解决许多看似复杂的子串/子数组问题。6. 常见问题与排查技巧实录在实际编写和调试这道题时我遇到过几个典型的“坑”。这里记录下来希望能帮你快速排雷。6.1 问题一结果总是比预期小或者为0可能原因1哈希表未正确初始化状态0的位置为-1。这是最常见的原因。如果忘记firstPos[0] -1;那么当整个字符串的前缀状态就是0时例如字符串开头就没有元音或者元音都成对出现算法会找不到匹配的状态从而错过从开头开始的最长子串。排查检查初始化代码。确保在遍历开始前执行了pos_map[0] -1;。可能原因2状态更新逻辑错误非元音字符也被翻转了状态。如果你错误地对所有字符都进行了异或操作或者掩码表设置错误导致非元音字符也对应了非零掩码那么状态就会在非元音处被意外修改导致整个状态序列完全错乱。排查在循环中打印每个字符处理后的state值与手动计算的结果对比。确保只有a, e, i, o, u五个字符会改变状态。可能原因3位掩码定义错误或混淆。例如把MASK_A定义为1 0但在判断时又按1 4来理解。这会导致状态计算完全不对。排查明确你的位顺序约定并在整个程序中保持一致。一个简单的测试输入字符串a遍历后state应该等于你定义的MASK_A。输入aa遍历后state应该变回0。6.2 问题二使用数组优化时访问越界可能原因掩码表mask[ch - a]访问时ch可能不是小写字母。题目说明只包含小写英文字母所以通常没问题。但如果输入有意外字符如调试时的手误ch - a可能为负数或大于25导致数组越界。排查在防御性编程中可以先判断ch是否在a到z之间。或者使用switch-case语句可以避免这个问题因为default分支会处理所有非元音字符。6.3 问题三理解不了为什么找到相同状态就是合法子串这是对算法核心逻辑理解不透彻的表现。技巧用一个极简的例子在纸上演算。 例如s ae。初始化state0,pos_map {0: -1}。遍历i0,cha更新state ^ MASK_A。假设MASK_A16state16。pos_map中没有16记录{0:-1, 16:0}。遍历i1,che更新state ^ MASK_E。假设MASK_E8state16^824。pos_map中没有24记录{0:-1, 16:0, 24:1}。结束。maxLen0。显然不对因为ae中每个元音出现1次奇数次不满足条件。再试s aa。初始化同上。i0,cha,state16。记录{0:-1, 16:0}。i1,cha,state16^160。pos_map中状态0已存在其位置是-1。计算长度i - (-1) 1 - (-1) 2。maxLen2。正确因为aa中a出现2次偶数次。这个例子清晰地展示了当状态回归到之前出现过的值时中间那段子串的净效果是让所有元音变化了偶数次。6.4 性能优化点与取舍哈希表 vs 数组如之前所述状态空间固定且很小32时用数组是更优选择。unordered_map有哈希开销而数组是O(1)的直接寻址。分支判断switch-case对于少量固定分支通常比查表如mask[ch-a]更快因为避免了减法和数组访问的开销且利于CPU分支预测。但在现代编译器优化下差异可能很小。代码清晰性更重要。循环内部操作将s.size()存入局部变量int n s.size()避免在循环条件中反复调用.size()函数虽然编译器可能会优化。对于追求极致性能的代码可以考虑这一点。6.5 调试与验证技巧打印状态流在循环内部打印i,ch,state以二进制形式。对比你手动计算的状态序列。bitset5 bs(state); // 需要 #include bitset cout i i , ch ch , state bs endl;单元测试准备几个小例子空字符串返回0。a最长子串是空串返回0。aa整个字符串aa满足条件返回2。ae没有满足条件的非空子串返回0。eleetminicoworoep力扣的示例答案是13leetminicowor。边界测试长字符串如全辅音、元音交替出现。确保算法在n500000时不会超时或内存溢出。这道题从暴力法的O(n^2)到最优解的O(n)其思维跨越是巨大的。它要求我们跳出“统计具体次数”的框框抓住“奇偶性”这个二元本质并用状态压缩和哈希表将问题转化。在面试中遇到如果能流畅地讲出这个推导过程并写出无bug的代码绝对能留下深刻的印象。多练习几遍直到你能在白板上毫不费力地写出精简版代码并解释清楚每一行背后的含义。