包含恰好 K 个不同元音的子字符串的数量
在这个问题中，我们需要计算字符串 str 中恰好包含 K 个不同元音的子字符串的总数。我们可以通过两种不同的方式解决这个问题。第一种方法是遍历所有子字符串并计算每个子字符串中的元音数量。我们还可以使用 map 数据结构来优化第一种方法的代码。
问题陈述– 我们给出了长度为 N 的字符串 str。该字符串包含大写和小写字母字符。另外，我们给出了整数 K。我们需要找到 str 中恰好包含 K 个不同元音的子字符串的总数。
注意– 在这里，我们假设"a"和"A"相等。
示例
输入– str = "point"，K = 2
输出– 6
解释– 恰好包含 2 个元音的 str 的子字符串为:'poi'、'oin'、'oint'、'poin'、'point' 和 'oi'。
输入– str = 'abcurso'，K = 3
输出– 1
解释– str 的子字符串恰好包含 3 个元音，即 str 本身。
输入– str = 'aeiofd', K = 5
输出– 0
解释– 由于字符串仅包含 4 个元音，因此我们需要一个包含 5 个元音的子字符串。因此，不可能找到任何子字符串。
方法 1
在此方法中，我们将获得长度为 1 到 N 的子字符串。我们将检查每个子字符串中的元音总数。如果我们发现任何子字符串恰好包含 K 个元音，我们将计数值增加 1。
算法
定义"cnt"变量以根据给定条件存储子字符串的数量，并定义"len"以存储字符串的长度。
使用两个嵌套循环覆盖 str 的所有子字符串。
从第 i 个索引开始获取子字符串，其长度为 (q – p + 1)。
使用 cntDistVowel() 函数计算子字符串中的不同元音。
在 cntDistVowel() 函数中，定义映射。
使用 transform() 将字符串转换为小写方法。
遍历字符串并更新字符串中每个字符的映射值。将值从 0 更新为 1。
从映射中返回"a"、"e"、"I"、"o"、"u"键的值的总和。
在 countKSub() 函数中，如果"dis_vowel"等于 K，则将"cnt"的值增加 1。
返回"cnt"值。
示例
#include <bits/stdc++.h>
using namespace std;
int cntDistVowel(string sub) {
// 创建 unordered_map 来存储子字符串中存在的元音
unordered_map<char, int> mp;
// 将 sub 转换为小写
transform(sub.begin(), sub.end(), sub.begin(), ::tolower);
// 遍历子字符串
for (int p = 0; p < sub.length(); p++) {
mp[sub[p]] = 1;
}
// 返回不同元音的总数
return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countkSubs(string str, int k) {
// 存储子字符串的总数
int cnt = 0;
int len = str.length();
// 遍历字符串
for (int p = 0; p < len; p++) {
for (int q = p; q < len; q++) {
// 获取从 p 到 q 的子字符串
string sub = str.substr(p, q - p + 1);
// 计算子字符串中的不同元音
int dis_vowel = cntDistVowel(sub);
// 如果不同元音的数量等于 k，则将 cnt 增加 1
if (dis_vowel == k)
cnt++;
}
}
return cnt;
}
int main() {
string str = "point";
int K = 2;
cout << "包含恰好 " << K << " 元音的子字符串数量为 " << countkSubs(str, K) << endl;
return 0;
}
输出
包含恰好 2 个元音的子字符串数量为 6
时间复杂度 – O(N*N*N)。这里，O(N*N) 用于查找所有子字符串，O(N) 用于计算最大长度为 N 的子字符串中的不同元音。
空间复杂度 – O(N)，因为我们使用"sub"变量来存储子字符串。
方法 2
此方法包含上述代码的优化版本。在这里，我们在从第 i 个索引开始遍历子字符串时更新映射中存在的字符。当我们找到任何包含恰好 K 个元音的子字符串时，我们会更新计数值。
算法
初始化"cnt"和"len"变量。
使用循环遍历字符串 str。
定义"dist_vowel"变量以存储从索引 p 开始的子字符串中的总不同元音。此外，定义 26 个列表以存储子字符串中元音的存在
使用嵌套循环获取 i 和 j 索引子字符串。
使用 tolower() 函数将字符转换为小写并将其存储到"temp"变量中。
– 使用 isVowel() 函数检查当前字符是否为 bowel。如果是，且不在映射中，则将 dist_vowel 的值增加 1。同时，更新映射的值。
如果"disst_vowel"的值等于 K，则增加"cnt"的值。
如果"dist_vowel"的值大于 K，则中断嵌套循环。
返回"cnt"的值。
示例
#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' );
}
int countkSubs(string alpha, int k) {
int len = alpha.length();
// 初始化计数
int cnt = 0;
// 覆盖所有子字符串
for (int p = 0; p < len; p++) {
// 存储不同元音的数量
int dist_vowel = 0;
// 存储字符的数量
vector<int> map(26, 0);
// 获取从 p 到 q 的子字符串
for (int q = p; q < len; q++) {
char temp = tolower(alpha[q]);
// 如果当前字符是元音并且是新的，则将 dist_vowel 增加 1
if (isVowel(temp) && map[temp - 'a'] == 0)
dist_vowel++;
// 将字符计数增加 1
map[temp - 'a']++;
// 如果不同元音的数量为 k，则将计数增加 1
if (dist_vowel == k)
cnt++;
// 如果不同元音的数量超过 k，则中断
if (dist_vowel > k)
break;
}
}
return cnt;
}
int main() {
string alpha = "point";
int K = 2;
cout << "包含恰好 " << K << " 元音的子字符串数量为 " << countkSubs(alpha, K) << endl;
return 0;
}
输出
包含恰好 2 个元音的子字符串数量为 6
时间复杂度 – O(N*N)，因为我们使用嵌套循环。
空间复杂度 – O(26) ~ O(1)，因为我们用于存储子字符串中元音的存在。
我们学习了两种解决问题的方法。第一种方法是朴素方法，第二种方法是优化方法。在这里，我们解决了计算包含恰好 K 个不同元音的子字符串数量的问题。程序员可以解决计算包含恰好 K 个元音的子字符串数量的问题。
