Given a string S of length N, the task is to find the number of non-empty substrings having even number of vowels.
Examples:
Input: N = 5, S = “abcde”
Output: 7
Explanation:
All possible substrings with even number of vowels are:
Substring Vowels
{abcde} 2
{b} 0
{bc} 0
{bcd} 0
{c} 0
{cd} 0
{d} 0
Input: N=4, S=”neveropen”
Output: 6
Naive Approach:
The simplest approach to solve the problem is to generate all possible substrings of the given string and for each substring, count the number of vowels and check if it is even or not. If found to be even, increase count. Finally, after checking for all substrings, print the value of count as the answer.
Below is the implementation of the above approach:
C++
// C++ program to implement//the above approach#include <bits/stdc++.h>using namespace std;// Utility function to check // if a character is a vowel bool isVowel(char c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function to calculate and return the// count of substrings with even number// of vowelsvoid countSubstrings(string s, int n){ // Stores the count of substrings int result = 0; for(int i = 0; i < n; i++) { int count = 0; for(int j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s[j])) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer cout << result;}// Driver Codeint main(){ int n = 5; string s = "abcde"; countSubstrings(s, n); return 0;}// This code is contributed by Amit Katiyar |
Java
// Java Program to implement// the above approachclass GFG { // Utility function to check // if a character is a vowel static boolean isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings int result = 0; for (int i = 0; i < n; i++) { int count = 0; for (int j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s.charAt(j))) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer System.out.println(result); } // Driver Code public static void main(String[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); }} |
Python3
# Python3 Program to implement# the above approach# Utility function to check# if a character is a voweldef isVowel(c): if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'): return True return False# Function to calculate and return the# count of substrings with even number# of vowelsdef countSubstrings(s, n): # Stores the count of substrings result = 0 for i in range(n): count = 0 for j in range(i, n): # If the current character # is a vowel if (isVowel(s[j])): #Increase count count += 1 # If substring contains # even number of vowels if (count % 2 == 0): #Increase the answer result += 1 # Print the final answer print(result)# Driver Codeif __name__ == '__main__': n = 5 s = "abcde" countSubstrings(s, n)# This code is contributed by Mohit Kumar |
C#
// C# program to implement// the above approachusing System;class GFG{// Utility function to check// if a character is a vowelstatic bool isVowel(char c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function to calculate and return the// count of substrings with even number// of vowelsstatic void countSubstrings(String s, int n){ // Stores the count of substrings int result = 0; for(int i = 0; i < n; i++) { int count = 0; for(int j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s[j])) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer Console.WriteLine(result);}// Driver Codepublic static void Main(String[] args){ int n = 5; String s = "abcde"; countSubstrings(s, n);}}// This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program to implement // the above approach // Utility function to check // if a character is a vowel function isVowel(c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels function countSubstrings(s, n) { // Stores the count of substrings let result = 0; for(let i = 0; i < n; i++) { let count = 0; for(let j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s[j])) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer document.write(result); } let n = 5; let s = "abcde"; countSubstrings(s, n); </script> |
Output:
7
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
Follow the steps below to optimize the above approach:
- Initialize a cumulative count modulo array temp[], such that:
temp[0] : Stores count of substrings having even number of vowels.
temp[1] : Stores count of substrings having odd number of vowels.
- Any substring [Si, Sj] will contain even number of vowels if the number of vowels in [S0, Si-1], and the number of vowels in [S0, Sj] have the same parity, i.e. either they are both even or both odd.
- Since the count of substrings with even number of vowels and odd number of vowels are stored in temp[], then, by using handshaking lemma:
Total count of substrings = (temp[0] * (temp[0] – 1))/2 + (temp[1] * (temp[1] – 1))/2
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Utility function to check// if a character is a vowelbool isVowel(char c){ if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false;}// Function to calculate and return the// count of substrings with even number// of vowelsvoid countSubstrings(string s, int n){ // Stores the count of substrings // with even and odd number of // vowels respectively int temp[] = { 1, 0 }; int result = 0, sum = 0; for(int i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s[i]) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); cout << result;}// Driver Codeint main(){ int n = 5; string s = "abcde"; countSubstrings(s, n);}// This code is contributed by Amit Katiyar |
Java
// Java Program to implement// the above approachclass GFG { // Utility function to check // if a character is a vowel static boolean isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings // with even and odd number of // vowels respectively int temp[] = { 1, 0 }; int result = 0, sum = 0; for (int i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s.charAt(i)) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); System.out.println(result); } // Driver Code public static void main(String[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); }} |
Python3
# Python3 program to implement# the above approach# Utility function to check# if a character is a voweldef isVowel(c): if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'): return True; return False;# Function to calculate and return the# count of substrings with even number# of vowelsdef countSubstrings(s, n): # Stores the count of substrings # with even and odd number of # vowels respectively temp = [1, 0]; result = 0; sum = 0; for i in range(0, n): # Update count of vowels modulo 2 # in sum to obtain even or odd sum += (1 if isVowel(s[i]) else 0); sum %= 2; # Increment even/odd count temp[sum] += 1; # Count substrings with even number # of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) // 2); result += ((temp[1] * (temp[1] - 1)) // 2); print(result);# Driver Codeif __name__ == '__main__': n = 5; s = "abcde"; countSubstrings(s, n);# This code is contributed by amal kumar choubey |
C#
// C# Program to implement// the above approachusing System;class GFG { // Utility function to check // if a character is a vowel static bool isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings // with even and odd number of // vowels respectively int []temp = { 1, 0 }; int result = 0, sum = 0; for (int i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s[i]) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); Console.Write(result); } // Driver Code public static void Main(string[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); }}// This code is contributed by rock_cool |
Javascript
<script> // Javascript program to implement // the above approach // Utility function to check // if a character is a vowel function isVowel(c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels function countSubstrings(s, n) { // Stores the count of substrings // with even and odd number of // vowels respectively let temp = [ 1, 0 ]; let result = 0, sum = 0; for(let i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s[i]) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); document.write(result); } let n = 5; let s = "abcde"; countSubstrings(s, n); // This code is contributed by divyeshrabadiya07.</script> |
Output:
7
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!
