The number of substrings of length K containing exactly X vowels

In this problem, we need to find the total number of substrings of length K that contain exactly K vowels. We will see two different ways to solve the problem. We can use a simple method to check the number of vowels in each substring of length K. Additionally, we can use a sliding window approach to solve this problem.

Problem Statement - We are given a string str of length N, containing lowercase and uppercase alphabetic characters. We need to count the total number of substrings of length K that contain exactly X vowels.

Example

Input– str = "TutorialsPoint", K = 3, X = 2

Output– 6

Explanation – Substrings of length 3 containing exactly 2 vowels are: 'uto', 'ori', 'ria', 'ial', 'Poi' and 'oin'. p>

Input– str = ‘aeiou’, K = 2, X = 2

Output– 4

Explanation-The substrings of length 2 and containing exactly 2 vowels are: ‘ae’, ‘ei’, ‘io’ and ‘ou’.

Input– str = ‘fghjsdfdffg’, K = 5, X = 1

Output– 0

Explanation - The string str does not contain any vowels, so we cannot find any substring containing 1 vowel.

method 1

In this method, we will find each substring of length K of str. After that, we will count the total number of vowels in a specific substring and if we find that they are equal to X, we can increase the count by 1.

algorithm

• In the cntSubStr() function, initialize the "cnt" variable to zero to store the total number of substrings.

• Use a loop to iterate from the 0th index to the len - K index, where "len" is the length of the string.

• In the loop, use the substr() method to obtain a substring of length K starting from the i-th index.

• Execute the countVowel() function to count the total number of vowels in the substring.

• In the countVowel() function, initialize the "vowels" variable to zero to store the total number of vowels.

• Traverse the substring, the current character is a vowel, add 1 to the value of ‘vowels’.

• Return "vowel".

• In the cntSubStr() function, if the total number of vowels in the substring is equal to X, increase the value of "cnt" by 1.

• Return the value of "cnt".

Example

#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;
}

Output

The total number of substrings of length 3 containing 2 vowels is 6

Time complexity– O(N*K), when we traverse str, traverse the substrings in the countVowel() function.

Space Complexity – O(K) since we store substrings

Method 2

We will use sliding window technology to solve the problems in this method. We will remove the first character from the substring and add 1 character at the end. Additionally, we'll keep track of the count of vowels in the current substring, and if it's equal to X, we can increment the count by 1.

algorithm

• Define the isVowel() function to return a Boolean value based on whether a specific character is a vowel.

• In the cntSubStr() function, define "total_vow" and initialize it to zero to store the total vowels in the current window.

• Starting from the 0th index, find the total number of vowels in the substring of length K, representing the first window.

• Initialize the "cnt" variable to 1 or 0 depending on whether the value of "vow" is equal to X.

• Start traversing the string from position 1 to len – K index.

• If the (i-1) character is a vowel, decrement the value of "total_vow" by 1.

• If the character at the (i - 1 K)th index is a vowel, increase the value of "total_vow" by 1.

• If "total_vow" equals X, increase "cnt" by 1.

• Return the value of "cnt".

Example

#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;
}

Output

The total number of substrings of length 3 containing 2 vowels is 6

Time complexity - O(N), since we iterate over the string.

Space complexity - O(1) since we don't use any extra space.

We optimized the second method and reduced the time complexity of the code. In addition, we also optimize the space complexity of the second method. Here we find the total number of substrings of length K that contain exactly X vowels, but the programmer could try to find the total number of substrings of any length that contain exactly K vowels.

The above is the detailed content of The number of substrings of length K containing exactly X vowels. For more information, please follow other related articles on the PHP Chinese website!