题目描述
给你一个字符串 word 和一个 非负 整数 k。
返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。
示例 1：
输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。
示例 2：
输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。
示例 3：
输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。word[6..11]，即 "qieaou"。word[7..12]，即 "ieaouq"。
提示：
5 <= word.length <= 250word 仅由小写英文字母组成。0 <= k <= word.length - 5
解法
方法一：问题转换 + 滑动窗口
我们可以转换为求以下两个问题：
- 求每个元音字母至少出现一次，且至少包含 $k$ 个辅音字母的子字符串的总数 $\textit{f}(k)$；
- 求每个元音字母至少出现一次，且至少包含 $k + 1$ 个辅音字母的子字符串的总数 $\textit{f}(k + 1)$。
那么答案就是 $\textit{f}(k) - \textit{f}(k + 1)$。
因此，我们设计一个函数 $\textit{f}(k)$，用于统计每个元音字母至少出现一次，且至少包含 $k$ 个辅音字母的子字符串的总数。
我们可以用一个哈希表 $\textit{cnt}$ 统计每个元音字母的出现次数，用一个变量 $\textit{ans}$ 统计答案，用一个变量 $\textit{l}$ 记录滑动窗口的左边界，用一个变量 $\textit{x}$ 记录当前窗口中辅音字母的个数。
遍历字符串，如果当前字符是元音字母，则将其加入哈希表 $\textit{cnt}$ 中，否则将 $\textit{x}$ 加一。如果此时 $\textit{x} \ge k$ 且哈希表 $\textit{cnt}$ 的大小为 $5$，说明当前窗口满足条件，我们循环移动左边界，直到窗口不满足条件。此时，以右边界 $\textit{r}$ 为结尾、且左边界在 $[0,.. \textit{l} - 1]$ 范围内的子字符串都满足条件，一共有 $\textit{l}$ 个。我们将 $\textit{l}$ 加到答案中。继续遍历字符串，直到遍历结束，我们就得到了 $\textit{f}(k)$。
最后，我们返回 $\textit{f}(k) - \textit{f}(k + 1)$。
时间复杂度 $O(n)$，其中 $n$ 是字符串 $\textit{word}$ 的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
def f(k: int) -> int:
cnt = Counter()
ans = l = x = 0
for c in word:
if c in "aeiou":
cnt[c] += 1
else:
x += 1
while x >= k and len(cnt) == 5:
d = word[l]
if d in "aeiou":
cnt[d] -= 1
if cnt[d] == 0:
cnt.pop(d)
else:
x -= 1
l += 1
ans += l
return ans
return f(k) - f(k + 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 | class Solution {
public int countOfSubstrings(String word, int k) {
return f(word, k) - f(word, k + 1);
}
private int f(String word, int k) {
int ans = 0;
int l = 0, x = 0;
Map<Character, Integer> cnt = new HashMap<>(5);
for (char c : word.toCharArray()) {
if (vowel(c)) {
cnt.merge(c, 1, Integer::sum);
} else {
++x;
}
while (x >= k && cnt.size() == 5) {
char d = word.charAt(l++);
if (vowel(d)) {
if (cnt.merge(d, -1, Integer::sum) == 0) {
cnt.remove(d);
}
} else {
--x;
}
}
ans += l;
}
return ans;
}
private boolean vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}
|
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 | class Solution {
public:
int countOfSubstrings(string word, int k) {
auto f = [&](int k) -> int {
int ans = 0;
int l = 0, x = 0;
unordered_map<char, int> cnt;
auto vowel = [&](char c) -> bool {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
};
for (char c : word) {
if (vowel(c)) {
cnt[c]++;
} else {
++x;
}
while (x >= k && cnt.size() == 5) {
char d = word[l++];
if (vowel(d)) {
if (--cnt[d] == 0) {
cnt.erase(d);
}
} else {
--x;
}
}
ans += l;
}
return ans;
};
return f(k) - f(k + 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 | func countOfSubstrings(word string, k int) int {
f := func(k int) int {
var ans int = 0
l, x := 0, 0
cnt := make(map[rune]int)
vowel := func(c rune) bool {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}
for _, c := range word {
if vowel(c) {
cnt[c]++
} else {
x++
}
for x >= k && len(cnt) == 5 {
d := rune(word[l])
l++
if vowel(d) {
cnt[d]--
if cnt[d] == 0 {
delete(cnt, d)
}
} else {
x--
}
}
ans += l
}
return ans
}
return f(k) - f(k+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 | function countOfSubstrings(word: string, k: number): number {
const f = (k: number): number => {
let ans = 0;
let l = 0,
x = 0;
const cnt = new Map<string, number>();
const vowel = (c: string): boolean => {
return c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u';
};
for (const c of word) {
if (vowel(c)) {
cnt.set(c, (cnt.get(c) || 0) + 1);
} else {
x++;
}
while (x >= k && cnt.size === 5) {
const d = word[l++];
if (vowel(d)) {
cnt.set(d, cnt.get(d)! - 1);
if (cnt.get(d) === 0) {
cnt.delete(d);
}
} else {
x--;
}
}
ans += l;
}
return ans;
};
return f(k) - f(k + 1);
}
|