包含恰好 X 个元音的 K 个长度子字符串的数量
在此问题中，我们需要找到包含恰好 K 个元音的长度为 K 的子字符串的总数。我们将看到两种不同的解决问题的方法。我们可以使用一种简单的方法，检查长度为 K 的每个子字符串中的元音数量。此外，我们还可以使用滑动窗口方法来解决问题。
问题陈述– 我们给出了一个长度为 N 的字符串 str，其中包含小写和大写字母字符。我们需要计算长度为 K 且恰好包含 X 个元音的子字符串的总数。
示例
输入– str = "TutorialsPoint", K = 3, X = 2
输出– 6
解释– 长度为 3 且恰好包含 2 个元音的子字符串为:'uto'、'ori'、'ria'、'ial'、'Poi' 和 'oin'。
输入– str = 'aeiou', K = 2, X = 2
输出– 4
解释– 长度为 2 且恰好包含 2 个元音的子字符串为:'ae'、'ei'、'io' 和'ou'。
输入– str = 'fghjsdfdffg', K = 5, X = 1
输出– 0
解释– 字符串 str 不包含任何元音，因此我们找不到包含 1 个元音的任何子字符串。
方法 1
在这种方法中，我们将找到 str 的长度为 K 的每个子字符串。之后，我们将计算特定子字符串中的元音总数，如果我们发现它们等于 X，我们可以将计数增加 1。
算法
在 cntSubStr() 函数中，用零初始化"cnt"变量以存储子字符串的总数。
使用循环从第 0 个索引开始迭代到 len - K 索引，其中"len"是字符串的长度。
在循环中，使用 substr() 方法从第 i 个索引开始获取长度为 K 的子字符串。
执行 countVowel() 函数来统计子字符串中元音的总数。
在 countVowel() 函数中，将'vowels'变量初始化为零，以存储元音的总数。
遍历子字符串，当前字符为元音，将'vowels'的值加 1。
返回'vowels'。
在 cntSubStr() 函数中，如果子字符串中的元音总数等于 X，则将'cnt'的值加 1。
返回'cnt'的值。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数用于计算字符串中元音的总数
int cntVowels(string alpha) {
int vows = 0;
for (int i = 0; i < alpha.length(); i++) {
if (alpha[i] == 'a' || alpha[i] == 'e' || alpha[i] == 'i' || alpha[i] == 'o' ||
alpha[i] == 'u' || alpha[i] == 'A' || alpha[i] == 'E' || alpha[i] == 'I' ||
alpha[i] == 'O' || alpha[i] == 'U')
vows++;
}
return vows;
}
int cntSubstr(string str, int K, int X) {
int cnt = 0;
// 遍历字符串并检查长度为 K 的每个子字符串中的元音总数
for (int i = 0; i <= str.length() - K; i++) {
// 从索引 i 开始获取长度为 K 的子字符串
string sub = str.substr(i, K);
// 检查子字符串中的元音总数是否等于 X，然后增加 cnt
if (cntVowels(sub) == X)
cnt++;
}
return cnt;
}
// 驱动代码
int main(void) {
string str = "TutorialsPoint";
int K = 3, X = 2;
cout << "The total number of substrings of length " << K << " containing " << X << " vowels is " << cntSubstr(str, K, X);
return 0;
}
输出
The total number of substrings of length 3 containing 2 vowels is 6
时间复杂度– O(N*K)，因为我们遍历 str，遍历 countVowel() 函数中的子字符串。
空间复杂度– O(K)，因为我们存储子字符串
方法 2
我们将使用滑动窗口技术来解决此方法中的问题。我们将从子字符串中删除第一个字符并在末尾添加 1 个字符。此外，我们将跟踪当前子字符串中的元音数量，如果它等于 X，我们可以将计数增加 1。
算法
定义 isVowel() 函数，根据特定字符是否为元音返回布尔值。
在 cntSubStr() 函数中，定义"total_vow"并用零初始化以存储当前窗口中的总元音。
从第 0 个索引开始查找长度为 K 的子字符串中的元音总数，代表第一个窗口。
根据"vow"的值是否等于 X，用 1 或 0 初始化"cnt"变量。
从第 1 个开始遍历字符串到第 2 个len – K 索引。
如果 (i-1) 个字符是元音，则将'total_vow' 的值减少 1。
如果 (i - 1 + K) 索引处的字符是元音，则将'total_vow' 的值增加 1。
如果'total_vow' 等于 X，则将'cnt' 增加 1。
返回'cnt' 的值。
示例
#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
// convert character to lowercase
ch = tolower(ch);
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
int cntSubstr(string str, int K, int X) {
// 存储总元音数
int total_vow = 0;
// 计算第一个窗口中的元音数
for (int p = 0; p < K; p++)
if (isVowel(str[p]))
total_vow++;
// 存储包含 X 个元音且长度为 K 的子字符串的总数
int cnt = 0;
// 如果第一个窗口恰好包含 X 个元音，则将 cnt 初始化为 1
cnt = total_vow == X ? 1 : 0;
// 遍历字符串
for (int i = 1; i <= str.length() - K; i++) {
// 从窗口中排除第 (i - 1) 个字符并更新 total_vow
total_vow = isVowel(str[i - 1]) ? total_vow - 1 : total_vow;
// 将第 [i-1+K] 个字符添加到当前窗口并更新 total_vow
total_vow = isVowel(str[i - 1 + K]) ? total_vow + 1 : total_vow;
// 如果当前窗口恰好包含 X 个元音，则增加 cnt
if (total_vow == X)
cnt++;
}
return cnt;
}
int main(void) {
string str = "TutorialsPoint";
int K = 3, X = 2;
cout << "包含 " << X << " 元音字母的长度为 " << K << " 的子字符串总数为 " << cntSubstr(str, K, X);
return 0;
}
输出
包含 2 个元音字母的长度为 3 的子字符串总数为 6
时间复杂度 – O(N)，因为我们遍历字符串。
空间复杂度 – O(1)，因为我们不使用任何额外空间。
我们优化了第二种方法，降低了代码的时间复杂度。此外，我们还优化了第二种方法的空间复杂度。这里，我们找到了总共包含恰好 X 个元音的长度为 K 的子字符串，但程序员可以尝试找到总共包含恰好 K 个元音的任意长度的子字符串。
