给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：
**输入：**s = “abciiidef”, k = 3
**输出：**3
**解释：**子字符串 “iii” 包含 3 个元音字母。
示例 2：
**输入：**s = “aeiou”, k = 2
**输出：**2
**解释：**任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：
**输入：**s = “leetcode”, k = 3
**输出：**2
解释：“lee”、”eet” 和 “ode” 都包含 2 个元音字母。
示例 4：
**输入：**s = “rhythms”, k = 4
**输出：**0
**解释：**字符串 s 中不含任何元音字母。
示例 5：
**输入：**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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
int maxVowels(string s, int k) {
int prev=0,befo=k-1,sum=0,ans=0;
string sub_string;
for(prev,befo;befo<s.length();prev++,befo++){
sub_string = s.substr(prev,k);
for(int i=prev;i<=befo;i++){
if(s[i] == 'a' ||
s[i] == 'e' ||
s[i] == 'i' ||
s[i] == 'o' ||
s[i] == 'u')
{
sum ++;
}
}
ans = max(sum,ans);
sum = 0;
}
return ans;
}
};
|
时间复杂度:$O(N · K)$ .
定长滑动窗口：
对于字符串$abci$ 假设已计算出子串$abc$ 的元音个数，则只需考虑删去的$a$ 是否为元音以及添加的$i$ 是否为元音。
对于 $s=abciiidef,k=3$
1
2
3
4
5
6
7
8
9
10
11
| 从左到右遍历 s。
首先统计前 k−1=2 个字母的元音个数，这有 1 个。
s[2]=c 进入窗口，此时找到了第一个长为 k 的子串 abc，现在元音个数有 1 个，更新答案最大值。然后 s[0]=a 离开窗口，现在元音个数有 0 个。
s[3]=i 进入窗口，此时找到了第二个长为 k 的子串 bci，现在元音个数有 1 个，更新答案最大值。然后 s[1]=b 离开窗口，现在元音个数有 1 个。
s[4]=i 进入窗口，此时找到了第三个长为 k 的子串 cii，现在元音个数有 2 个，更新答案最大值。然后 s[2]=c 离开窗口，现在元音个数有 2 个。
s[5]=i 进入窗口，此时找到了第四个长为 k 的子串 iii，现在元音个数有 3 个，更新答案最大值。然后 s[3]=i 离开窗口，现在元音个数有 2 个。
s[6]=d 进入窗口，此时找到了第五个长为 k 的子串 iid，现在元音个数有 2 个，更新答案最大值。然后 s[4]=i 离开窗口，现在元音个数有 1 个。
s[7]=e 进入窗口，此时找到了第六个长为 k 的子串 ide，现在元音个数有 2 个，更新答案最大值。然后 s[5]=i 离开窗口，现在元音个数有 1 个。
s[8]=f 进入窗口，此时找到了第七个长为 k 的子串 def，现在元音个数有 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
| class Solution {
public:
int maxVowels(string s, int k) {
int i=0,sum=0,ans=0;
for(int i=0;i<s.length();i++){
if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') sum++;
if(i < k-1) continue;
ans = max(sum,ans);
int out = s[i - k + 1];
if(out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') sum--;
}
return ans;
}
};
|
时间复杂度：$O(N)$