https://www.nowcoder.com/profile/803722233/codeBookDetail?submissionId=136202727

前缀和 + 状态压缩

前缀和

每个子串对应着一个区间，那么有什么方法可以在不重复遍历子串的前提下，快速求出这个区间里指定字母出现的次数呢？
答案就是前缀和，对于一个区间，我们可以用两个前缀和的差值，得到其中某个字母的出现次数。

思路和算法

• 首先题目中要求子字符串中每个指定字母恰好出现偶数次，我们就可以使用 0 和 1 来标识每个字母的状态(偶数次或奇数次)，我们不需要知道每个字母出现的完整次数，只需要知道这个次数的奇偶性
• 那么我们可以注意到奇数次 + 1 = 偶数次，偶数次 + 1 = 奇数次，所以我们可以使用 异或（无进位相加 ） 来参与运算： 比如 aba
• 初始时 status = 00000，然后到 a 的时候 00000 ^ 00001 = 00001，1 说明 a 出现奇数次
• 然后到 b 的时候 00001 ^ 00010 = 00011，两个 1 说明 a、b 都出现奇数次
• 最后到 a 的时候 00011 ^ 00001 = 00010，说明只有 b 出现奇数次了。
• 以上也说明我们确实是可以使用状态码去标识每个字母出现次数的奇偶性。
• 那么我们怎么去统计最长子串的长度呢？
• 首先我们先盘盘哪些子串符合要求，因为现在每个下标对应的状态码其实也就只有 0 和 1
• 如果坐标 i 对应的状态码是 00011，坐标 j 对应的状态码是 00011，那么他们俩中间的元音字母数一定是偶数，如果某一位不相同，那么绝对不可能是偶数，因为偶数-奇数=奇数，奇数-偶数=奇数
• 所以我们每次求出一个坐标的状态码的时候就去瞅瞅这个状态码前面是否存在，如果存在，那么就计算一下之间子字符串的长度就 ok 了，那么我们还需要啥？明显需要一个hash表，存储每个状态码对应的下标！当然因为我们状态码最长也就是 11111 = 2^5 - 1 = 31，开一个 32 大小的数组就好了。