C++ 包含恰好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;

// 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)，因为我们遍历字符串时，在countVowel()函数中遍历子字符串。

空间复杂度 - O(K)，因为我们存储了子字符串。

方法2

在这个方法中，我们将使用滑动窗口技术来解决这个问题。我们将从子字符串中移除第一个字符，并在末尾添加1个字符。同时，我们将跟踪当前子字符串中元音字母的数量，如果等于X，我们将增加计数器。

步骤

• 定义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)，因为我们没有使用额外的空间。

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