原题
给你一个字符串 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^5s只包含小写英文字母。
解法
思想
使用官方题解的前缀和+状态压缩！
这道题不好想，如果用暴力在leetcode绝对超时，可以想到用前缀和的方法。
前缀和怎么做呢？如果要两个字符串的差值（字符串交集）中，a,e,i,o,u全部为偶数，那么根据数学知识，偶数减偶数是偶数，奇数减奇数也是偶数。也就是说两个字符串中的这五个字母出现的奇偶性必须一样！
而五个字母，每个字母出现的次数都可奇可偶，组合出来的情况有很多种，在遍历的时候遇到其中一种奇偶性组合，如何知道最早出现的同一种奇偶性组合出现在哪个位置呢？
这里有一种方法：遍历的时候记录并计算所有字母的个数，然后对每次遍历到的位置，将它的奇偶性组合编码成字符串，例如“奇偶奇偶奇”，代表a,i,u出现奇数个，而e,o出现偶数个。然后就以这个字符串为键，第一次出现的顺序为值存放到哈希表中。后面只要出现相同的奇偶性排列，就把它从哈希表中取出来，就知道最早出现的位置，两个位置一减就是字符串的长度。
但是这种方法需要构造字符串，并且需要记录五种字母出现的个数，十分麻烦，那么可以利用“状态压缩”+“位运算”的方法：将这种奇偶性排列编码成一个五位的二进制位串，例如二进制的"10101"，代表a,i,u出现奇数个，而e,o出现偶数个。每一个字母都映射到位串的一个位上，而再出现一个字母的时候，就通过异或运算更改对应位上的值。
例如： "10101" :a,i,u出现奇数个，e,o出现偶数个
（再出现一个i）->"10101"^"100" = "10001"，即a,u出现奇数个，e,i,o出现偶数个。
代码
class Solution {
public int findTheLongestSubstring(String s) {
int n = s.length();
int[] pos = new int[1 << 5];
// 如果是-1，说明还没有出现这种奇偶性排列
Arrays.fill(pos, -1);
int ans = 0, status = 0;
//第一个全偶的情况出现在还没开始遍历的时候
pos[0] = 0;
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == 'a') {
status ^= (1 << 0);
} else if (ch == 'e') {
status ^= (1 << 1);
} else if (ch == 'i') {
status ^= (1 << 2);
} else if (ch == 'o') {
status ^= (1 << 3);
} else if (ch == 'u') {
status ^= (1 << 4);
}
if (pos[status] >= 0) {
ans = Math.max(ans, i + 1 - pos[status]);
} else {
pos[status] = i + 1;
}
}
return ans;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1371-%e6%af%8f%e4%b8%aa%e5%85%83%e9%9f%b3%e5%8c%85%e5%90%ab%e5%81%b6%e6%95%b0%e6%ac%a1%e7%9a%84%e6%9c%80%e9%95%bf%e5%ad%90%e5%ad%97%e7%ac%a6%e4%b8%b2/
