力扣：3305.元音辅音字符串计数
给你一个字符串
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
解题思路
要解决这个问题，我们需要找到所有满足以下条件的子字符串：
- 包含所有五个元音字母（‘a’, ‘e’, ‘i’, ‘o’, ‘u’）。
- 恰好包含 k 个辅音字母。
关键步骤分析：
- 滑动窗口遍历：使用双重循环遍历所有可能的子字符串。外层循环确定子字符串的起始位置
i，内层循环扩展子字符串的结束位置j。 - 辅音计数：在内层循环中，维护当前子字符串的辅音数量。若辅音数量超过 k，则提前终止当前起始位置的遍历。
- 元音掩码：使用位掩码（
mask）来记录当前子字符串中出现的元音。每遇到一个元音，设置对应的位。 - 条件检查：当辅音数量恰好为 k 时，检查位掩码是否为
0x1F（二进制11111，表示所有五个元音均存在），若满足则计数加一。
class Solution {
public:
int countOfSubstrings(string word, int k) {
int count = 0;
int n = word.size();
for (int i = 0; i < n; ++i) {
int consonants = 0;
int mask = 0;
for (int j = i; j < n; ++j) {
char c = word[j];
if (isVowel(c)) {
int bit = getVowelBit(c);
mask |= (1 << bit);
} else {
++consonants;
if (consonants > k) break;
}
if (consonants == k && mask == 0x1F) {
++count;
}
}
}
return count;
}
private:
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int getVowelBit(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;
}
}
};上述时间复杂度：O（n^2)
空间复杂度：O(1)，仅使用常数空间存储辅音计数和元音掩码。
位掩码（Bitmask）的定义
位掩码是一种利用二进制位（0或1）表示状态或标志的技术。通过将多个布尔值压缩到一个整数中，每个二进制位代表一个独立的状态（例如权限、开关等），从而高效地管理和操作多个状态。
位掩码的核心用途
- 状态压缩
将多个二元状态（如“是/否”）合并到一个整数中，节省内存。- 快速查询与修改
通过位运算（AND、OR、NOT等）快速检查或修改特定状态。- 组合与筛选
灵活组合不同状态，例如权限系统的“读+写+执行”组合。
官方题解
方法一：暴力枚举
枚举字符串 word 的所有子字符串，统计每个元音字母都出现且辅音字母出现次数等于 k 的子字符串数目。
class Solution {
public:
long long countOfSubstrings(string word, int k) {
set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
int n = word.size();
long long res = 0;
for (int i = 0; i < n; i++) {
set<char> occur;
int consonants = 0;
for (int j = i; j < n; j++) {
if (vowels.count(word[j])) {
occur.insert(word[j]);
} else {
consonants++;
}
if (occur.size() == vowels.size() && consonants == k) {
res++;
}
}
}
return res;
}
};
复杂度分析
时间复杂度：O(n^2)，其中 n 是 word 的长度。
空间复杂度：O(1)。
方法二：滑动窗口
令 count(k) 表示每个元音字母至少出现一次，并且至少包含 k 个辅音字母的子字符串的总数，那么本问题的答案等于 count(k)−count(k+1)。对于 count(k)，我们可以使用滑动窗口来求解。
对于区间 [i,j) 内的子字符串，我们依次枚举子字符串的左端点 i，对于对应的右端点 j，我们不断地右移右端点 j，直到区间 [i,j) 对应的子字符满足每个元音字母至少出现一次，并且至少包含 k 个辅音字母，或者 j=n。右移操作完成后，如果区间 [i,j) 内的子字符串满足每个元音字母至少出现一次，并且至少包含 k 个辅音字母，那么左端点为 i 的子字符串满足条件的数目为 n−j+1。count(k) 即为所有数目之和。
class Solution {
public:
long long countOfSubstrings(string word, int k) {
set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
auto count = [&](int m) -> long long {
int n = word.size(), consonants = 0;
long long res = 0;
map<char, int> occur;
for (int i = 0, j = 0; i < n; i++) {
while (j < n && (consonants < m || occur.size() < vowels.size())) {
if (vowels.count(word[j])) {
occur[word[j]]++;
} else {
consonants++;
}
j++;
}
if (consonants >= m && occur.size() == vowels.size()) {
res += n - j + 1;
}
if (vowels.count(word[i])) {
occur[word[i]]--;
if (occur[word[i]] == 0) {
occur.erase(word[i]);
}
} else {
consonants--;
}
}
return res;
};
return count(k) - count(k + 1);
}
};
复杂度分析
时间复杂度：O(n)，其中 n 是 word 的长度。
空间复杂度：O(1)。
作者：力扣官方题解
链接：https://leetcode.cn/problems/count-of-substrings-containing-every-vowel-and-k-consonants-i/solutions/3077748/yuan-yin-fu-yin-zi-fu-chuan-ji-shu-i-by-r8rjy/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
ps:本问题的答案等于 count(k)−count(k+1)