05 August 2008
Given the string 1
s
Example 1:
1
2
3
Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.
Example 2:
1
2
3
Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.
Example 3:
1
2
3
Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.
Constraints:
1
1 <= s.length <= 5 x 10^5
1
s
遇到找最大最小字串问题，第一反应滑动窗口行不行。 但是很快这个想法就被否定了，因为滑动窗口（这里是可变滑动窗口）需要扩张和收缩窗口大小，这样做起来比较麻烦。因为题目要求的是奇偶性，而不是类似“元音出现最多的子串”等。
1) 没了思路，那就试试暴力法吧。暴力法的思路比较朴素和直观。 那就是双层循环找到所有子串，然后对于每一个子串，统计元音个数，如果子串的元音个数都是偶数，则更新答案，最后返回最大的满足条件的子串长度即可。暴力可以用一个小的 trick。枚举所有子串的时候，从最长的子串开始枚举的，这样找到一个满足条件的直接返回就行了（early return），不必再去找较小的子串以及维护最大值。
暴力法可以通过测试。
2) 上面暴力法思路中对于每一个子串，统计元音个数，仔细观察的话，会发现有很多重复的统计。那么优化这部分的内容就可以获得更好的效率。
对于这种连续的数字问题，这里考虑使用前缀和来优化，做预处理。
经过这种空间换时间的策略之后，时间复杂度会降低到O(n ^ 2)，但是相应空间复杂度会上升到O(n)，这种取舍在很多情况下是值得的。
3) 前面的前缀和思路，通过空间（prefix）换取时间的方式降低了时间复杂度。但是时间复杂度仍然是平方，是否可以继续优化呢？
实际上由于我们只关心元音出现的奇偶性，并不关心每一个元音字母具体出现的次数。因此可以使用1
是奇数，是偶数
使用 5 位的二进制来表示以 i 结尾的字符串中包含各个元音的奇偶性，其中 0 表示偶数，1 表示奇数，并且最低位表示 a，然后依次是 e，i，o，u。比如 1
10110
为什么用 0 表示偶数？1 表示奇数？
其实这个解法还用到了一个性质，这个性质是小学数学知识：
看到这里，1
为什么用 0 表示偶数？1 表示奇数？
如果对两个二进制做异或，会对其每一位进行位运算，如果相同则位 0，否则位 1。这和上面的性质非常相似。上面说1
奇偶性相同则位偶数，否则为奇数
1
用 0 表示偶数？1 表示奇数
时间复杂度O(n)，空间复杂度O(n)。
暴力法，O(n ^ 3)
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
class Solution {
public int findTheLongestSubstring(String s) {
int len = s.length();
char[] vowels = {'a', 'e', 'i', 'o', 'u'};
for (int i = len; i >= 0; i--) { // i是offset，从最长的字符串长度len开始
for (int j = 0; j < len - i + 1; j++) {// j是起点
String sub = s.substring(j, j + i); // 从最长字符串开始
boolean has_odd_vowel = false;
for (char vowel : vowels) { // 逐个检查每个元音
if (countVowel(sub, vowel) % 2 != 0) {
has_odd_vowel = true;
break;
}
}
if (!has_odd_vowel) { // early return
return i;
}
}
}
return 0;
}
private int countVowel (String sub, char ch) {
int result = 0;
for (int k = 0; k < sub.length(); k++) {
if (ch == sub.charAt(k)) {
result++;
}
}
return result;
}
}
前缀和+剪枝，O(n ^ 2)
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public int findTheLongestSubstring(String s) {
int len = s.length();
if (len == 0) {
return 0;
}
int[][] preSum = new int[len][5]; // 记录5个元音字母的出现次数
// 初始化
int start = getIndex(s.charAt(0)); // 找到当前字符在数组中的位置
if (start != -1) {
preSum[0][start]++;
}
// 计算字符串中每个位置的preSum
for (int i = 1; i < len; i++) {
int index = getIndex(s.charAt(i));
for (int j = 0; j < 5; j++) { //index分别为0，1，2，3，4
if (index == j) { // 遇到元音，长度+1
preSum[i][j] = preSum[i - 1][j] + 1;
} else { // 遇到辅音
preSum[i][j] = preSum[i - 1][j];
}
}
}
for (int i = len - 1; i >= 0; i--) { // offset
for (int j = 0; j < len - i; j++) {
if (checkValid(preSum, s, j, j + i)) { // [)
return i + 1;
}
}
}
return 0;
}
public boolean checkValid(int[][] preSum, String s, int left, int right) {
int index = getIndex(s.charAt(left));
for (int k = 0; k < 5; k++) {
if (((preSum[right][k] - preSum[left][k] + (index == k ? 1 : 0)) & 1) == 1) { //根据存储的信息，相减计算当前字串是否有偶数的元音
return false;
}
}
return true;
}
private int getIndex(char ch) {
if (ch == 'a')
return 0;
else if (ch == 'e')
return 1;
else if (ch == 'i')
return 2;
else if (ch == 'o')
return 3;
else if (ch == 'u')
return 4;
else
return -1;
}
}
前缀和+状态压缩，O(n)
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
class Solution {
HashMap<Character, Integer> vowlToBitIndex = new HashMap<Character, Integer>() {
{
put('a', 1);
put('e', 2);
put('i', 4);
put('o', 8);
put('u', 16);
}
};
public int findTheLongestSubstring(String s) {
HashMap<Integer, Integer> stateToIndex = new HashMap<>();
stateToIndex.put(0, -1);
int state = 0, maxLen = 0;
for(int i = 0; i < s.length(); ++i) {
char cur = s.charAt(i);
if(vowlToBitIndex.containsKey(cur)) {
// flap the digits of the state. 1-> 0 or 0 -> 1
int bitToFlip = vowlToBitIndex.get(cur);
state ^= bitToFlip;
}
stateToIndex.putIfAbsent(state, i);
maxLen = Math.max(maxLen, i - stateToIndex.get(state));
}
return maxLen;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
mapper = {
"a": 1,
"e": 2,
"i": 4,
"o": 8,
"u": 16
}
seen = {0: -1}
res = cur = 0
for i in range(len(s)):
if s[i] in mapper:
cur ^= mapper.get(s[i])
# 全部奇偶性都相同，相减一定都是偶数
if cur in seen:
res = max(res, i - seen.get(cur))
else:
seen[cur] = i
return res