统计美妙子串数量的O(n)算法原理咨询及代码解析需求

核心思路：状态压缩+前缀异或 #

• 状态压缩：题目限定字符串仅包含前10个小写字母，我们可以用1位二进制数表示单个字母的出现奇偶性：0代表出现偶数次，1代表出现奇数次。10个字母刚好可以用一个长度为10的整数表示整体状态，总共有2^10=1024种可能的状态，数量非常有限。
• 前缀异或性质：定义mask[i]为字符串前i个字符（下标0到i-1）的奇偶性状态，那么子串[l, r]（闭区间，对应下标l到r）的状态等于mask[r+1] ^ mask[l]。因为异或运算的特性是相同为0、不同为1，两个前缀状态异或的结果，刚好对应中间子串每个字母的奇偶性差异。
• 美妙子串判定转换：美妙子串要求状态中最多有1个1，也就是mask[r+1] ^ mask[l]满足以下两个条件之一：
  1. 结果为0：所有字母出现次数都是偶数，对应mask[r+1] == mask[l]
  2. 结果只有1位为1：仅一个字母出现奇数次，对应mask[l] == mask[r+1] ^ (1 << k)，其中k取值为0~9（对应a到j）

对应代码逻辑拆解 #

你给出的C++代码完全遵循上述思路，每一步逻辑对应如下：

1. 初始化：mp用于统计每个前缀状态的出现次数，初始时空前缀的状态为0，所以mp[0] = 1。
2. 遍历字符串的每个字符，更新当前前缀状态xorsum：每遇到字符c，就翻转对应位的奇偶性，即xorsum ^= 1 << (c-'a')。
3. 统计第一种合法情况：查询mp中当前xorsum的出现次数，累加到答案中，这些次数就是所有满足mask[l] == 当前mask的l的数量，对应所有字母都是偶数次的美妙子串。
4. 统计第二种合法情况：遍历0~9共10位，计算翻转某一位后的临时状态temp = xorsum ^ (1<<i)，查询mp中temp的出现次数，累加到答案中，这些次数对应仅第i个字母出现奇数次的美妙子串。
5. 把当前的前缀状态xorsum加入mp，计数加1，供后续前缀查询使用。

示例验证（输入aba） #

我们用示例输入走一遍代码逻辑，验证结果正确性：

1. 初始状态：ans=0，xorsum=0，mp={0:1}
2. 处理第一个字符a：
   • xorsum更新为0 ^ 1 = 1
   • 查询mp中1的计数为0，ans累加0
   • 遍历10位，仅当i=0时temp=1^1=0，mp中0的计数为1，ans累加1，当前ans=1
   • 把xorsum=1加入mp，mp={0:1,1:1}
3. 处理第二个字符b：
   • xorsum更新为1 ^ 2 = 3
   • 查询mp中3的计数为0，ans累加0
   • 遍历10位，仅当i=1时temp=3^2=1，mp中1的计数为1，ans累加1，当前ans=2
   • 把xorsum=3加入mp，mp={0:1,1:1,3:1}
4. 处理第三个字符a：
   • xorsum更新为3 ^ 1 = 2
   • 查询mp中2的计数为0，ans累加0
   • 遍历10位：i=0时temp=2^1=3，mp计数为1，ans加1；i=1时temp=2^2=0，mp计数为1，ans加1，当前ans=4
   • 把xorsum=2加入mp
     最终返回ans=4，和示例输出完全一致。

优化提示 #

因为状态总数只有1024种，完全可以用长度为1024的数组代替unordered_map，避免哈希表的开销，运行速度会更快，实现也更简单。

内容的提问来源于stack exchange，提问作者sachin