前缀和之奇偶篇
本篇文章总结两个关于「前缀和」结合「奇偶」，同时又包含「异或」的题目！！
关于「前缀和」以及「异或」的总结可见：
最美子字符串的数目
题目详情可见 最美子字符串的数目
题目要求计算出字符串中至多一个字母出现奇数次的所有子串数量，所以会有两种情况：
- 子串所有字母出现的次数全都是偶数
- 子串只有一个字母出现的次数是奇数
而且题目中还有一个额外的附加条件：字符串中的字符由前十个小写英文字母组成
由于只需要知道一个字母出现次数的奇偶性，而不需要知道一个字母到底出现了多少次
所以可以用一个长度为 10 位的数字表示某一个子串中各字母出现的奇偶次数，如果出现次数为偶数，则该位为 0，否则为 1
正好可以利用「异或」运算的特点，0 ^ 1 = 1; 1 ^ 1 = 0
上面描述的可能比较抽象，具体看图：
最终可以得到二机制为0000110000的值为字符串accaefffdd的奇偶性表示。显然，这不是一个符合要求的字符串
分析第一种情况
但如果可以在accaefffdd的所有以a开头的子串中找到一个奇偶性为0000110000的子串x，那么显然字符串accaefffdd去除x后剩下的子串肯定符合要求
从「异或」的角度分析，0000110000 ^ 0000110000 = 0，显然剩下的子串中字母出现的次数均为偶数
从具体的例子分析，accaef的奇偶性表示为0000110000，和原字符串相同，所以去除accaef后剩下的字符串为ffdd，显然符合要求
上面分析的都是第一种情况，即：子串所有字母出现的次数全都是偶数。我们的目标统计奇偶性完全相同的数量
分析第二种情况
下面分析第二种情况，即：子串只有一个字母出现的次数是奇数，其实也差不多，只需找出只有一位不同的奇偶性数量即可
从具体的例子分析，accae的奇偶性表示为0000010000，和原字符串只有一位不同，所以去除accae后剩下的字符串为fffdd，显然符合第二种情况
处理技巧
最后还有一个处理的技巧，由于 10 位即可表示出所有的情况，所以可以用一个大小为 1024 的数组来统计每种情况的数量
具体代码
xxxxxxxxxxpublic long wonderfulSubstrings(String word) { // 统计每种情况的个数 int[] cnt = new int[1024]; // 全 0 的情况 cnt[0] = 1; // 记录字符串的奇偶性 int sum = 0; long ans = 0L; for (int i = 0; i < word.length(); i++) { // 更新奇偶性 sum ^= 1 << ((int) word.charAt(i) - 'a'); // 累加第一种情况的数量 ans += cnt[sum]; // 累加第二种情况的数量 for (int j = 1; j < 1024; j <<= 1) { ans += cnt[sum ^ j]; } // 更新数量 cnt[sum]++; } return ans;}找出最长的超赞子字符串
题目详情可见 找出最长的超赞子字符串
这个题目其实和上一个题目相似度有 90%
首先一个字符串需要可以变成回文子串，回文子串有两种情况：
- 偶数情况：
aabb - 奇数情况：
aabcc
所以刚好对应上题的两种情况
不同的在于，本题需要统计的不是每种情况出现的数量，而是每种情况最先出现的下标
为什么是最先出现的下标呢？因为需要计算最长的超赞子字符串的长度
public int longestAwesome(String s) { // 统计每种情况最先出现的下标 int[] cnt = new int[1024]; // 初始位 -2 Arrays.fill(cnt, -2); // 原因：aa 的奇偶性表示为 0，当前下标为 1，所以长度为 1 - cnt[0] = 1 - (-1) = 2 cnt[0] = -1; int sum = 0, ans = -1; for (int i = 0; i < s.length(); i++) { sum ^= 1 << ((int) s.charAt(i) - '0'); // 已经出现该情况，且为偶数 if (cnt[sum] != -2) ans = Math.max(ans, i - cnt[sum]); // 已经出现该情况，且为奇数 for (int j = 1; j < 1024; j <<= 1) { if (cnt[sum ^ j] != -2) ans = Math.max(ans, i - cnt[sum ^ j]); } // 记录首次出现下标 if (cnt[sum] == -2) cnt[sum] = i; } return ans;}