题目简介：
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例 1：
1
2
3
| 输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
|
示例 2：
1
2
3
| 输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
|
示例 3：
1
2
3
| 输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
|
提示：
1 <= s.length <= 5 x 10^5s 只包含小写英文字母。
思路：
使用状态压缩：
a对应二进制数 00001 -> 1e对应二进制数 00010 -> 2i对应二进制数 00100 -> 4o对应二进制数 01000 -> 8u对应二进制数 10000 -> 16
所以出现相对应的字符时，异或相应的数，得到相应的值，范围为0 ~ 31
1
2
3
4
5
6
7
8
9
| 如果state=0：则元音字母都没出现 00000
如果state=1：则a出现奇数次 00001
如果state=2：则e出现奇数次 00010
如果state=3：则a e出现奇数次 00011
如果state=4: 则i出现奇数次 00100
如果state=5: 则a i出现奇数次 00101
如果state=6: 则e i 出现奇数次 00110
...
如果state=31: 则所有元音字母出现奇数次 11111
|
所以分为两种情况，若是第一次遇到state所代表的数，则将当前下标存入pos[state]，否则，则说明之前已经遇到过该数了，则之前一次的结束下标为pos[state]，当前结束下标为i，则s[pos[state]]……s[i]之间的数异或结果为0，说明这段字符串a,e,i,o,u出现次数为偶数次(a^a = 0)，所以拿i - pos[state]和max_length比较取最大值即可。
tip：
pos[0]需要等于-1，因为首字符不为元音字符时，i - pos[state] = 0 - (-1) = 1。 即元音字符均出现0次(符合偶数次)，长度为1。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
int findTheLongestSubstring(string s) {
int max_length = 0;
vector<int> pos(32, -2);
pos[0] = -1;
int state = 0;
for(int i = 0; i < s.length(); i++){
switch(s[i]){
case 'a':
state ^= 1;
break;
case 'e':
state ^= 2;
break;
case 'i':
state ^= 4;
break;
case 'o':
state ^= 8;
break;
case 'u':
state ^= 16;
break;
default:
break;
}
if(pos[state] == -2)
pos[state] = i;
else
max_length = max(max_length, i - pos[state]);
}
return max_length;
}
};
|
