第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
1371.每个元音包含偶数次的最长子字符串

题目描述

1
给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。
2
3
4
5
示例 1:
6
7
输入:s = "eleetminicoworoep"
8
输出:13
9
解释:最长子字符串是 "leetminicowor" ,它包含 e,i,o 各 2 个,以及 0 个 a,u 。
10
示例 2:
11
12
输入:s = "leetcodeisgreat"
13
输出:5
14
解释:最长子字符串是 "leetc" ,其中包含 2 个 e 。
15
示例 3:
16
17
输入:s = "bcbcbc"
18
输出:6
19
解释:这个示例中,字符串 "bcbcbc" 本身就是最长的,因为所有的元音 a,e,i,o,u 都出现了 0 次。
20
21
22
提示:
23
24
1 <= s.length <= 5 x 10^5
25
s 只包含小写英文字母。
Copied!

前置知识

暴力法 + 剪枝

公司

  • 暂无

思路

首先拿到这道题的时候,我想到第一反应是滑动窗口行不行。 但是很快这个想法就被我否定了,因为滑动窗口(这里是可变滑动窗口)我们需要扩张和收缩窗口大小,而这里不那么容易。因为题目要求的是奇偶性,而不是类似“元音出现最多的子串”等。
突然一下子没了思路。那就试试暴力法吧。暴力法的思路比较朴素和直观。 那就是双层循环找到所有子串,然后对于每一个子串,统计元音个数,如果子串的元音个数都是偶数,则更新答案,最后返回最大的满足条件的子串长度即可
这里我用了一个小的 trick。枚举所有子串的时候,我是从最长的子串开始枚举的,这样我找到一个满足条件的直接返回就行了(early return),不必维护最大值。这样不仅减少了代码量,还提高了效率。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def findTheLongestSubstring(self, s: str) -> int:
3
for i in range(len(s), 0, -1):
4
for j in range(len(s) - i + 1):
5
sub = s[j:j + i]
6
has_odd_vowel = False
7
for vowel in ['a', 'e', 'i', 'o', 'u']:
8
if sub.count(vowel) % 2 != 0:
9
has_odd_vowel = True
10
break
11
if not has_odd_vowel: return i
12
return 0
Copied!
复杂度分析
  • 时间复杂度:双层循环找出所有子串的复杂度是$O(n^2)$,统计元音个数复杂度也是$O(n)$,因此这种算法的时间复杂度为$O(n^3)$。
  • 空间复杂度:$O(1)$

前缀和 + 剪枝

思路

上面思路中对于每一个子串,统计元音个数,我们仔细观察的话,会发现有很多重复的统计。那么优化这部分的内容就可以获得更好的效率。
对于这种连续的数字问题,这里我们考虑使用前缀和来优化。
经过这种空间换时间的策略之后,我们的时间复杂度会降低到$O(n ^ 2)$,但是相应空间复杂度会上升到$O(n)$,这种取舍在很多情况下是值得的。

代码

代码支持:Python3,Java
Python3 Code:
1
class Solution:
2
i_mapper = {
3
"a": 0,
4
"e": 1,
5
"i": 2,
6
"o": 3,
7
"u": 4
8
}
9
def check(self, s, pre, l, r):
10
for i in range(5):
11
if s[l] in self.i_mapper and i == self.i_mapper[s[l]]: cnt = 1
12
else: cnt = 0
13
if (pre[r][i] - pre[l][i] + cnt) % 2 != 0: return False
14
return True
15
def findTheLongestSubstring(self, s: str) -> int:
16
n = len(s)
17
18
pre = [[0] * 5 for _ in range(n)]
19
20
# pre
21
for i in range(n):
22
for j in range(5):
23
if s[i] in self.i_mapper and self.i_mapper[s[i]] == j:
24
pre[i][j] = pre[i - 1][j] + 1
25
else:
26
pre[i][j] = pre[i - 1][j]
27
for i in range(n - 1, -1, -1):
28
for j in range(n - i):
29
if self.check(s, pre, j, i + j):
30
return i + 1
31
return 0
Copied!
Java Code:
1
class Solution {
2
public int findTheLongestSubstring(String s) {
3
4
int len = s.length();
5
6
if (len == 0)
7
return 0;
8
9
int[][] preSum = new int[len][5];
10
int start = getIndex(s.charAt(0));
11
if (start != -1)
12
preSum[0][start]++;
13
14
// preSum
15
for (int i = 1; i < len; i++) {
16
17
int idx = getIndex(s.charAt(i));
18
19
for (int j = 0; j < 5; j++) {
20
21
if (idx == j)
22
preSum[i][j] = preSum[i - 1][j] + 1;
23
else
24
preSum[i][j] = preSum[i - 1][j];
25
}
26
}
27
28
for (int i = len - 1; i >= 0; i--) {
29
30
for (int j = 0; j < len - i; j++) {
31
if (checkValid(preSum, s, j, i + j))
32
return i + 1;
33
}
34
}
35
return 0;
36
}
37
38
39
public boolean checkValid(int[][] preSum, String s, int left, int right) {
40
41
int idx = getIndex(s.charAt(left));
42
43
for (int i = 0; i < 5; i++)
44
if (((preSum[right][i] - preSum[left][i] + (idx == i ? 1 : 0)) & 1) == 1)
45
return false;
46
47
return true;
48
}
49
public int getIndex(char ch) {
50
51
if (ch == 'a')
52
return 0;
53
else if (ch == 'e')
54
return 1;
55
else if (ch == 'i')
56
return 2;
57
else if (ch == 'o')
58
return 3;
59
else if (ch == 'u')
60
return 4;
61
else
62
return -1;
63
}
64
}
Copied!
复杂度分析
  • 时间复杂度:$O(n^2)$。
  • 空间复杂度:$O(n)$

前缀和 + 状态压缩

思路

前面的前缀和思路,我们通过空间(prefix)换取时间的方式降低了时间复杂度。但是时间复杂度仍然是平方,我们是否可以继续优化呢?
实际上由于我们只关心奇偶性,并不关心每一个元音字母具体出现的次数。因此我们可以使用是奇数,是偶数两个状态来表示,由于只有两个状态,我们考虑使用位运算。
我们使用 5 位的二进制来表示以 i 结尾的字符串中包含各个元音的奇偶性,其中 0 表示偶数,1 表示奇数,并且最低位表示 a,然后依次是 e,i,o,u。比如 10110 则表示的是包含偶数个 a 和 o,奇数个 e,i,u,我们用变量 cur 来表示。
为什么用 0 表示偶数?1 表示奇数?
回答这个问题,你需要继续往下看。
其实这个解法还用到了一个性质,这个性质是小学数学知识:
  • 如果两个数字奇偶性相同,那么其相减一定是偶数。
  • 如果两个数字奇偶性不同,那么其相减一定是奇数。
看到这里,我们再来看上面抛出的问题为什么用 0 表示偶数?1 表示奇数?。因为这里我们打算用异或运算,而异或的性质是:
如果对两个二进制做异或,会对其每一位进行位运算,如果相同则位 0,否则位 1。这和上面的性质非常相似。上面说奇偶性相同则位偶数,否则为奇数。因此很自然地用 0 表示偶数?1 表示奇数会更加方便。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def findTheLongestSubstring(self, s: str) -> int:
3
mapper = {
4
"a": 1,
5
"e": 2,
6
"i": 4,
7
"o": 8,
8
"u": 16
9
}
10
seen = {0: -1}
11
res = cur = 0
12
13
for i in range(len(s)):
14
if s[i] in mapper:
15
cur ^= mapper.get(s[i])
16
# 全部奇偶性都相同,相减一定都是偶数
17
if cur in seen:
18
res = max(res, i - seen.get(cur))
19
else:
20
seen[cur] = i
21
return res
Copied!
复杂度分析
  • 时间复杂度:$O(n)$。
  • 空间复杂度:$O(n)$

关键点解析

  • 前缀和
  • 状态压缩

相关题目