最多包含 X 个不同元音的 K 长度子字符串的计数
在此问题中，我们需要找到最多包含 X 个不同元音的长度为 K 的子字符串的总数。我们可以通过两种不同的方式解决问题。第一种方法是获取所有子字符串并计算每个长度为 K 的子字符串中的不同元音。第二种方法是使用映射数据结构并跟踪特定子字符串中的不同元音数量。
问题陈述– 我们给出了长度为 N 的字符串 str。该字符串仅包含字母字符。此外，我们给出了 K 和 X 个正整数。我们需要找到总共包含最多 X 个不同元音的长度为 K 的不同子字符串。
示例
输入– str = 'point', K = 3, X = 2
输出– 3
解释– 长度为 3 且最多包含 2 个不同元音的子字符串为 −
字符串 'poi' 包含 2 个元音。
字符串 'oin' 包含两个元音。
字符串 'int' 包含 1 个元音。
输入– str = 'sdfgh', K = 3, X = 2
输出– 0
解释– 该字符串不包含任何元音，因此输出为零。
输入– str = 'aeiou', K = 2, X = 2
输出– 4
解释– 长度为 2 且最多包含 2 个不同元音的子字符串为:'ae'、'ei'、'io' 和 'ou'。
方法 1
在这种方法中，我们将从给定的字符串中获取每个长度为 K 的子字符串。之后，我们将检查子字符串中不同元音的数量，并根据子字符串包含的元音总数返回结果值。
算法
初始化"cnt"和"len"变量。
开始遍历字符串，从第0个索引遍历到len-k索引。
使用substr()方法从索引i开始获取长度为K的子字符串。
使用countDistVowels()函数计算子字符串中的不同元音。
在countDistVowels()函数中，使用map存储特定元音的存在。
访问从映射中查找 a、e、I、o 和 u 键并返回它们的和。
如果子字符串中不同元音的总数小于 K，则将"cnt"值增加 1。
当循环的所有迭代完成后，返回"cnt"值。
示例
#include <bits/stdc++.h>
using namespace std;
int countDistVowels(string str){
int dist = 0;
int len = str.length();
// 映射以存储元音的存在
unordered_map<char, int> mp;
// 在映射中插入元音
for (int i = 0; i < len; i++){
mp[str[i]] = 1;
}
// 返回字符串中不同元音的数量
return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countSubStr(string str, int K, int X){
// 存储符合给定条件的总子字符串
int cnt = 0;
int len = str.size();
for (int i = 0; i <= len - K; i++){
// 获取长度为 K 的子字符串
string s = str.substr(i, K);
// 如果 contDistVowels() 函数返回的值小于 X，则将 cnt 加 1。
if (countDistVowels(s) <= X){
cnt++;
}
}
return cnt;
}
int main(void){
string str = "point";
int K = 3, X = 2;
cout << "长度为 K 且最多包含 X 个不同元音的子字符串的数量为 " << countSubStr(str, K, X);
return 0;
}
输出
长度为 K 且最多包含 X 个不同元音的子字符串的数量为 3
时间复杂度 – O(N*K)，因为我们计算每个子字符串中的不同元音
空间复杂度 – O(K)，因为我们存储长度为 K 的子字符串。
方法 2
此方法使用滑动窗口技术来解决问题。我们可以计算第一个窗口中不同元音的总数，之后，我们在更新窗口中的字符时不断更新不同元音的数量。
算法
定义"vow"变量并用零初始化。另外，定义映射来存储元音频率
将字符串转换为小写。
从索引 0 开始，计算长度为 K 的第一个子字符串中不同元音的总数。
如果"vow"的值小于或等于 X，则将"cnt"值初始化为 1。否则为 0。
从第 1 个到第 len – k 个索引遍历字符串。
如果第 (I – 1) 个字符是元音，则将"vow"的值减少 1 并更新其在映射中的频率。
我们需要将第 (I – 1 + K) 个字符插入当前窗口。如果它是元音，并且它在映射中的频率为零，则将"vow"增加 1 并更新映射中的频率，因为它是当前窗口中的不同元音。
如果"vow"的值小于 X，则将"cnt"增加 1。
将"cnt"的值返回 1。
示例
#include <bits/stdc++.h>
using namespace std;
// 检查给定字符是否为元音
bool isVowel(char ch) {
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
// 函数用于计算最多包含 k 个元音且长度为 k 的子字符串的数量
int countSubStr(string alpha, int K, int X) {
// 存储元音的数量
int vow = 0;
// 创建一个无序映射来存储元音的数量
unordered_map<char, int> mp;
// 将字符串转换为小写
transform(alpha.begin(), alpha.end(), alpha.begin(), ::tolower);
// 在长度为 k 的字符串中存储总的不同元音
for (int i = 0; i < K; i++) {
if (isVowel(alpha[i]) && mp[alpha[i]] == 0) {
vow++;
mp[alpha[i]]++;
}
}
// 如果第一个子字符串最多包含 x 个元音，则将 cnt 增加 1
int cnt = vow <= X ? 1 : 0;
for (int i = 1; i <= alpha.length() -K; i++) {
// 从当前窗口删除第 i-1 个字符
if (isVowel(alpha[i - 1])) {
vow--;
mp[alpha[i - 1]]--;
}
// 插入第 (i - 1 + K) 个字符
if (isVowel(alpha[i - 1 + K]) && mp[alpha[i - 1 + K]] == 0) {
vow++;
mp[alpha[i - 1 + K]]++;
}
if (vow <= X)
cnt++;
}
return cnt;
}
int main(void) {
string str = "point";
int K = 3, X = 2;
cout << "长度为 K 且最多包含 X 个不同元音的子字符串的数量为 " << countSubStr(str, K, X);
return 0;
}
输出
长度为 K 且最多包含 X 个不同元音的子字符串的数量为 3
时间复杂度 – O(N)，因为我们遍历字符串。
空间复杂度 – O(1)，因为我们使用常数空间。
我们使用两种方法解决了这个问题。第二种方法使用滑动窗口技术来优化代码。程序员可以尝试计算最多包含 X 个不同元音的任意长度的子字符串的总数，并对此类问题进行更多练习。
