Given string str of N characters containing both uppercase and lowercase English alphabets, the task is to find the count of substrings of size K containing exactly X vowels.
Examples:
Input: str = “GeeksForGeeks”, K = 2, X = 2
Output: 2
Explanation: The given string only contains 2 substrings of size 2 consisting of 2 vowels. They are “ee” and “ee”.Input: str = “TrueGeek”, K = 3, X = 2
Output: 5
Approach: The given problem can be solved using a sliding window technique by maintaining a window of size K and keeping track of the number of vowels encountered in the current window. If the count of vowels in the current window is equal to X, increment the final required count by 1.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;#define MAX 128// Function to check whether// a character is vowel or notbool isVowel(char x){ return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to find the count of// K-sized substring having X vowelsint cntSubstr(string str, int K, int X){ // Stores the number of vowels // in the current window int vow = 0; for (int i = 0; i < K; i++) if (isVowel(str[i])) vow++; // Stores the count of K length // substring with X vowels int ans = vow == X ? 1 : 0; for (int i = 1; i < str.length(); i++) { // Remove (i - 1)th character // from the current window vow = isVowel(str[i - 1]) ? vow - 1 : vow; // Insert (i - 1 + K)th character // from the current window vow = isVowel(str[i - 1 + K]) ? vow + 1 : vow; if (vow == X) // Increment answer ans++; } // Return Answer return ans;}// Driver codeint main(void){ string s = "TrueGeek"; int K = 3, X = 2; cout << cntSubstr(s, K, X); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;class GFG{ // Function to check whether // a character is vowel or not static boolean isVowel(char x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the count of // K-sized subString having X vowels static int cntSubstr(String str, int K, int X) { // Stores the number of vowels // in the current window int vow = 0; for (int i = 0; i < K; i++) if (isVowel(str.charAt(i))) vow++; // Stores the count of K length() // subString with X vowels int ans = vow == X ? 1 : 0; for (int i = 1; i < str.length(); i++) { // Remove (i - 1)th character // from the current window vow = isVowel(str.charAt(i - 1)) ? vow - 1 : vow; // Insert (i - 1 + K)th character // from the current window if(i - 1 + K < str.length()) vow = isVowel(str.charAt(i - 1 + K)) ? vow + 1 : vow; if (vow == X) // Increment answer ans++; } // Return Answer return ans; } // Driver code public static void main (String[] args) { String s = "TrueGeek"; int K = 3, X = 2; System.out.println(cntSubstr(s, K, X)); }}// This code is contributed by Shubham Singh |
Python3
# Python3 program of the above approachMAX = 128# Function to check whether# a character is vowel or notdef isVowel(x): return(x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u' or x == 'A' or x == 'E' or x == 'I' or x == 'O' or x == 'U')# Function to find the count of# K-sized substring having X vowelsdef cntSubstr(str, K, X): # Stores the number of vowels # in the current window vow = 0 for i in range(0, K): if (isVowel(str[i])): vow += 1 # Stores the count of K length # substring with X vowels ans = 1 if vow == X else 0 for i in range(1, len(str) - K + 1): # Remove (i - 1)th character # from the current window vow = vow - 1 if isVowel(str[i - 1]) else vow # Insert (i - 1 + K)th character # from the current window vow = vow + 1 if isVowel(str[i - 1 + K]) else vow if (vow == X): # Increment answer ans += 1 # Return Answer return ans# Driver codeif __name__ == "__main__": s = "TrueGeek" K, X = 3, 2 print(cntSubstr(s, K, X))# This code is contributed by rakeshsahni |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to check whether // a character is vowel or not static bool isVowel(char x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the count of // K-sized substring having X vowels static int cntSubstr(string str, int K, int X) { // Stores the number of vowels // in the current window int vow = 0; for (int i = 0; i < K; i++) if (isVowel(str[i])) vow++; // Stores the count of K length // substring with X vowels int ans = vow == X ? 1 : 0; for (int i = 1; i < str.Length; i++) { // Remove (i - 1)th character // from the current window vow = isVowel(str[i - 1]) ? vow - 1 : vow; // Insert (i - 1 + K)th character // from the current window if(i - 1 + K < str.Length) vow = isVowel(str[i - 1 + K]) ? vow + 1 : vow; if (vow == X) // Increment answer ans++; } // Return Answer return ans; } // Driver code public static void Main() { string s = "TrueGeek"; int K = 3, X = 2; Console.Write(cntSubstr(s, K, X)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach let MAX = 128 // Function to check whether // a character is vowel or not function isVowel(x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the count of // K-sized substring having X vowels function cntSubstr(str, K, X) { // Stores the number of vowels // in the current window let vow = 0; for (let i = 0; i < K; i++) if (isVowel(str[i])) vow++; // Stores the count of K length // substring with X vowels let ans = vow == X ? 1 : 0; for (let i = 1; i < str.length; i++) { // Remove (i - 1)th character // from the current window vow = isVowel(str[i - 1]) ? vow - 1 : vow; // Insert (i - 1 + K)th character // from the current window vow = isVowel(str[i - 1 + K]) ? vow + 1 : vow; if (vow == X) // Increment answer ans++; } // Return Answer return ans; } // Driver code let s = "TrueGeek"; let K = 3, X = 2; document.write(cntSubstr(s, K, X)); // This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(N)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
