题目描述
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：
1
2
3
| 输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
|
示例 2：
1
2
3
| 输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
|
示例 3：
1
2
3
| 输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
|
示例 4：
1
2
3
| 输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
|
示例 5：
1
2
| 输入：s = "tryhard", k = 4
输出：1
|
提示：
1 <= s.length <= 10^5s 由小写英文字母组成1 <= k <= s.length
题解
思路：使用滑动窗口，依次遍历，然后取得最大值。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int maxVowels(string s, int k) {
// 创建映射表，便于以logn的复杂度查找
std::set<char> vowel{'a', 'e', 'i', 'o', 'u'};
int begin{};
int end = k;
int max{};
while (end <= s.size()) {
int num{};
for (int i = begin; i < end; ++i) {
if (auto it = vowel.find(s[i]); it != vowel.end()) {
num++;
}
}
begin++;
end++;
if (num > max)
max = num;
}
return max;
}
};
|
这个解法的问题是时间复杂度过高，导致超时。
解法二：
这里封装了一个函数，用于方便判断是否为元音字母。同时将vowel映射设置为内联静态成员变量，以提高性能。
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
| class Solution {
inline static std::set<char> vowel{'a', 'e', 'i', 'o', 'u'};
bool isVowel(char c) {
if (auto it = vowel.find(c); it != vowel.end()) {
return true;
}
return false;
}
public:
int maxVowels(string s, int k) {
int max{};
for (int i = 0; i < k; i++) {
if (isVowel(s[i])) {
max++;
}
}
int num = max;
for (int i = k; i < s.size(); ++i) {
if (isVowel(s[i - k])) {
num--;
}
if (isVowel(s[i])) {
num++;
}
// 比较交换最大数值
max = std::max(num, max);
}
return max;
}
};
|
