力扣：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 <= 250
word 仅由小写英文字母组成。
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)