Keshawn_lu's Blog

Leetcode 1371. 每个元音包含偶数次的最长子字符串

字数统计: 695阅读时长: 3 min
2020/05/20 Share

题目简介:

给你一个字符串 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^5
  • s 只包含小写英文字母。

思路:

使用状态压缩:

  • a对应二进制数 00001 -> 1
  • e对应二进制数 00010 -> 2
  • i对应二进制数 00100 -> 4
  • o对应二进制数 01000 -> 8
  • u对应二进制数 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;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: