Medium
题目描述
给你一个字符串 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 <= 2 * 10^5word仅由小写英文字母组成0 <= k <= word.length - 5
解题思路
这道题要求找到包含所有5个元音字母且恰好包含k个辅音字母的子字符串数量。我们可以使用滑动窗口结合二分查找的方法来解决。
核心思路：
- 对于每个右端点
r，我们需要找到满足条件的左端点范围 - 满足条件的子字符串需要：包含所有5个元音字母 + 恰好k个辅音字母
- 可以转化为：恰好k个辅音的数量 - 恰好k-1个辅音的数量
具体实现：
- 定义辅助函数
atMostK(word, k)，计算最多包含k个辅音且包含所有元音的子字符串数量 - 使用滑动窗口维护当前窗口内的元音和辅音数量
- 当窗口满足"包含所有元音且辅音数量≤k"时，所有以当前右端点结尾、左端点在[left, r]范围内的子字符串都满足条件
- 最终答案 =
atMostK(word, k) - atMostK(word, k-1)
时间复杂度分析：
- 每次调用
atMostK的时间复杂度为O(n) - 总时间复杂度为O(n)，其中n是字符串长度
代码实现
class Solution {
public:
long long countOfSubstrings(string word, int k) {
return atMostK(word, k) - atMostK(word, k - 1);
}
private:
long long atMostK(string& word, int k) {
if (k < 0) return 0;
int n = word.length();
int vowelCount[5] = {0}; // a, e, i, o, u
int consonants = 0;
int left = 0;
long long result = 0;
for (int right = 0; right < n; right++) {
char c = word[right];
if (isVowel(c)) {
vowelCount[getVowelIndex(c)]++;
} else {
consonants++;
}
while (consonants > k) {
char leftChar = word[left];
if (isVowel(leftChar)) {
vowelCount[getVowelIndex(leftChar)]--;
} else {
consonants--;
}
left++;
}
while (hasAllVowels(vowelCount) && consonants <= k) {
result += right - left + 1;
char leftChar = word[left];
if (isVowel(leftChar)) {
vowelCount[getVowelIndex(leftChar)]--;
} else {
consonants--;
}
left++;
}
}
return result;
}
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int getVowelIndex(char c) {
switch(c) {
case 'a': return 0;
case 'e': return 1;
case 'i': return 2;
case 'o': return 3;
case 'u': return 4;
default: return -1;
}
}
bool hasAllVowels(int vowelCount[]) {
for (int i = 0; i < 5; i++) {
if (vowelCount[i] == 0) return false;
}
return true;
}
};
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
def atMostK(k):
if k < 0:
return 0
vowel_count = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
consonants = 0
left = 0
result = 0
for right in range(len(word)):
c = word[right]
if c in vowel_count:
vowel_count[c] += 1
else:
consonants += 1
while consonants > k:
left_char = word[left]
if left_char in vowel_count:
vowel_count[left_char] -= 1
else:
consonants -= 1
left += 1
while all(count > 0 for count in vowel_count.values()) and consonants <= k:
result += right - left + 1
left_char = word[left]
if left_char in vowel_count:
vowel_count[left_char] -= 1
else:
consonants -= 1
left += 1
return result
return atMostK(k) - atMostK(k - 1)
public class Solution {
public long CountOfSubstrings(string word, int k) {
return AtMostK(word, k) - AtMostK(word, k - 1);
}
private long AtMostK(string word, int k) {
if (k < 0) return 0;
int n = word.Length;
int[] vowelCount = new int[5]; // a, e, i, o, u
int consonants = 0;
int left = 0;
long result = 0;
for (int right = 0; right < n; right++) {
char c = word[right];
if (IsVowel(c)) {
vowelCount[GetVowelIndex(c)]++;
} else {
consonants++;
}
while (consonants > k) {
char leftChar = word[left];
if (IsVowel(leftChar)) {
vowelCount[GetVowelIndex(leftChar)]--;
} else {
consonants--;
}
left++;
}
while (HasAllVowels(vowelCount) && consonants <= k) {
result += right - left + 1;
char leftChar = word[left];
if (IsVowel(leftChar)) {
vowelCount[GetVowelIndex(leftChar)]--;
} else {
consonants--;
}
left++;
}
}
return result;
}
private bool IsVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
private int GetVowelIndex(char c) {
return c switch {
'a' => 0,
'e' => 1,
'i' => 2,
'o' => 3,
'u' => 4,
_ => -1
};
}
private bool HasAllVowels(int[] vowelCount) {
for (int i = 0; i < 5; i++) {
if (vowelCount[i] == 0) return false;
}
return true;
}
}
var countOfSubstrings = function(word, k) {
const atMostK = (k) => {
if (k < 0) return 0;
const vowelCount = {a: 0, e: 0, i: 0, o: 0, u: 0};
let consonants = 0;
let left = 0;
let result = 0;
for (let right = 0; right < word.length; right++) {
const c = word[right];
if (c in vowelCount) {
vowelCount[c]++;
} else {
consonants++;
}
while (consonants > k) {
const leftChar = word[left];
if (leftChar in vowelCount) {
vowelCount[leftChar]--;
} else {
consonants--;
}
left++;
}
while (hasAllVowels(vowelCount) && consonants <= k) {
result += right - left + 1;
const leftChar = word[left];
if (leftChar in vowelCount) {
vowelCount[leftChar]--;
} else {
consonants--;
}
left++;
}
}
return result;
};
const hasAllVowels = (vowelCount) => {
return Object.values(vowelCount).every(count => count > 0);
};
return atMostK(k) - atMostK(k - 1);
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n)，其中 n 是字符串长度。虽然有嵌套循环，但每个字符最多被访问常数次 |
| 空间复杂度 | O(1)，只使用了固定大小的数组/哈希表存储元音字母计数 |