LeetCode 题解工作台
元音辅音字符串计数 I
给你一个字符串 word 和一个 非负 整数 k 。 返回 word 的 子字符串 中，每个元音字母（ 'a' 、 'e' 、 'i' 、 'o' 、 'u' ） 至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。 示例 1： 输入： word = "aeioqq", k = 1 输…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
我们可以转换为求以下两个问题： 1. 求每个元音字母至少出现一次，且至少包含 个辅音字母的子字符串的总数 ；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个字符串 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
解题思路
方法一：问题转换 + 滑动窗口
我们可以转换为求以下两个问题：
- 求每个元音字母至少出现一次，且至少包含 个辅音字母的子字符串的总数 ；
- 求每个元音字母至少出现一次，且至少包含 个辅音字母的子字符串的总数 。
那么答案就是 。
因此，我们设计一个函数 ，用于统计每个元音字母至少出现一次，且至少包含 个辅音字母的子字符串的总数。
我们可以用一个哈希表 统计每个元音字母的出现次数，用一个变量 统计答案，用一个变量 记录滑动窗口的左边界，用一个变量 记录当前窗口中辅音字母的个数。
遍历字符串，如果当前字符是元音字母，则将其加入哈希表 中，否则将 加一。如果此时 且哈希表 的大小为 ，说明当前窗口满足条件，我们循环移动左边界，直到窗口不满足条件。此时，以右边界 为结尾、且左边界在 范围内的子字符串都满足条件，一共有 个。我们将 加到答案中。继续遍历字符串，直到遍历结束，我们就得到了 。
最后，我们返回 。
时间复杂度 ，其中 是字符串 的长度。空间复杂度 。
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for sliding through the string with constant-time hash map updates per letter. Space complexity is O(1) for the hash map since vowels are limited and consonant counting uses constant space. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check that all vowels exist before counting the substring.
- question_mark
Watch for off-by-one errors when managing the window boundaries.
- question_mark
Confirm consonant count matches exactly k while expanding or shrinking.
常见陷阱
外企场景- error
Forgetting to remove consonants when shrinking the window.
- error
Counting windows that include all vowels but exceed k consonants.
- error
Using nested loops for substring generation instead of sliding window.
进阶变体
外企场景- arrow_right_alt
Count substrings containing all vowels and at most k consonants.
- arrow_right_alt
Count substrings containing all vowels and a range of consonants from k to m.
- arrow_right_alt
Count substrings containing all vowels and exactly k specific consonants only.