包含恰好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。

• 返回“元音”。

• 在 cntSubStr() 函数中，如果子字符串中的元音总数等于 X，则将“cnt”的值增加 1。

• 返回“cnt”的值。

示例

#include <bits/stdc++.h>
using namespace std;

// function to count the total number of vowels in a string
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;
   // traverse the string and check for the total number of vowels in each substring of length K
    for (int i = 0; i <= str.length() - K; i++) {
       // get the substring of length K starting from index i
       string sub = str.substr(i, K);
       // check if the total number of vowels in the substring is equal to X, then increment cnt
       if (cntVowels(sub) == X)
          cnt++;
   }
   return cnt;
}
// Driver code
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，将“cnt”变量初始化为1或0。

• 开始从第 1 个位置遍历字符串到 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) {
   // To store total vowels
   int total_vow = 0;
   // Count the number of vowels in the first window
   for (int p = 0; p < K; p++)
       if (isVowel(str[p]))
            total_vow++;
   // to store the total number of substrings of length K containing X vowels
   int cnt = 0;
   // If the first window contains exactly X vowels, initialize cnt as 1
   cnt = total_vow == X ? 1 : 0;
   // traverse the string
   for (int i = 1; i <= str.length() - K; i++) {
      // exclude the (i - 1)th character from the window and update the total_vow
      total_vow = isVowel(str[i - 1]) ? total_vow - 1 : total_vow;
      // Add [i-1+K]th character to the current window and update total_vow
      total_vow = isVowel(str[i - 1 + K]) ? total_vow + 1 : total_vow;
      // If the current window contains exactly X vowels, increment cnt
      if (total_vow == 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)，因为我们遍历字符串。

空间复杂度 - O(1)，因为我们不使用任何额外的空间。

我们优化了第二种方法并降低了代码的时间复杂度。此外，我们还优化了第二种方法的空间复杂度。在这里，我们找到了恰好包含 X 个元音字母的长度为 K 的子串总数，但是程序员可以尝试找到恰好包含 K 个元音字母的任意长度的子串总数。