Maximize count of Substrings containing at least 1 vowel and 1 consonant
Given a string S consisting of only lowercase English letters of length N, the task is to find the count of substrings such that each substring contains at least 1 vowel and 1 consonant.
Examples:
Input: S = “happybirthday”
Output: 3
Explanation: S can be divided as “ha”, “ppybi”, “rthday”Input: S = “w3wiki”
Output 5
Explanation: S can be divided as “ge“, “ek“, “sfo“, “rge”, “eks”
Approach: To solve the problem follow the below idea:
The idea is to apply the greedy approach, traverse the string, and every time we encounter 1 vowel and 1 consonant increase the count by 1 and reset the number of vowels and consonants to 0.
Follow the steps below to solve the problem:
- Initialize variable ans = 0, haveVowels = false (current string have vowels or not), haveConsonants = false (current string have consonants or not)
- Travel over the string by each character
- If current character is vowels make the haveVowels = true else haveConsonants = true
- Whenever both are true then consider current subsegment is a valid substring, increase ans by 1, make haveVowels = false and haveConsonants = false.
Below is the implementation of the above approach.
C++
#include <iostream> using namespace std; int strengthOfString(string S) { int ans = 0; int N = S.size(); // For checking at least 1 vowels // and 1 consonants bool haveVowels = false ; bool haveConsonants = false ; // Travel over the loop for ( int i=0;i<N;i++) { // Check current letter have // vowels or not if (S[i]== 'a' ||S[i]== 'e' ||S[i]== 'i' ||S[i]== 'o' ||S[i]== 'u' ) haveVowels = true ; else haveConsonants = true ; // Both the type of letter are present // then increase the ans count if (haveVowels && haveConsonants) { ans += 1; haveVowels = false ; haveConsonants = false ; } } // Return the main ans return ans; } int main() { string S = "happybirthday" ; // Function Call int ans = strengthOfString(S); cout << ans; return 0; } //this code is contributed by aditya942003patil |
Java
// Java program to implement the approach import java.io.*; class GFG { public static int strengthOfString(String S) { int ans = 0 ; int N = S.length(); // For checking at least 1 vowels // and 1 consonants boolean haveVowels = false ; boolean haveConsonants = false ; // Travel over the loop for ( int i = 0 ; i < N; i++) { // Check current letter have // vowels or not if (S.charAt(i) == 'a' || S.charAt(i) == 'e' || S.charAt(i) == 'i' || S.charAt(i) == 'o' || S.charAt(i) == 'u' ) haveVowels = true ; else haveConsonants = true ; // Both the type of letter are present // then increase the ans count if (haveVowels == true && haveConsonants == true ) { ans += 1 ; haveVowels = false ; haveConsonants = false ; } } // Return the main ans return ans; } // Driver Code public static void main(String[] args) { String S = "happybirthday" ; // Function Call int ans = strengthOfString(S); System.out.print(ans); } } // This code is contributed by Rohit Pradhan |
Python3
# Python program to implement the approach # Function to calculate maximum # strength of a string def strengthOfString(S): ans = 0 N = len (S) # For checking at least 1 vowels # and 1 consonants haveVowels = False haveConsonants = False # Travel over the loop for s in S: # Check current letter have # vowels or not if s in "aeiou" : haveVowels = True else : haveConsonants = True # Both the type of letter are present # then increase the ans count if haveVowels and haveConsonants: ans + = 1 haveVowels = False haveConsonants = False # Return the main ans return ans # Driver Code if __name__ = = "__main__" : S = "happybirthday" # Function Call ans = strengthOfString(S) print (ans) |
C#
// C# program to implement the approach using System; public class GFG { public static int strengthOfString(String S) { int ans = 0; int N = S.Length; // For checking at least 1 vowels // and 1 consonants bool haveVowels = false ; bool haveConsonants = false ; // Travel over the loop for ( int i = 0; i < N; i++) { // Check current letter have // vowels or not if (S[i] == 'a' || S[i] == 'e' || S[i] == 'i' || S[i] == 'o' || S[i] == 'u' ) haveVowels = true ; else haveConsonants = true ; // Both the type of letter are present // then increase the ans count if (haveVowels == true && haveConsonants == true ) { ans += 1; haveVowels = false ; haveConsonants = false ; } } // Return the main ans return ans; } static public void Main() { // Code string S = "happybirthday" ; // Function Call int ans = strengthOfString(S); Console.Write(ans); } } // This code is contributed by lokeshmvs21. |
Javascript
<script> // JavaScript code for the above approach function strengthOfString(S) { let ans = 0; let N = S.length; // For checking at least 1 vowels // and 1 consonants let haveVowels = false ; let haveConsonants = false ; // Travel over the loop for (let i = 0; i < N; i++) { // Check current letter have // vowels or not if (S.charAt(i) == 'a' || S.charAt(i) == 'e' || S.charAt(i) == 'i' || S.charAt(i) == 'o' || S.charAt(i) == 'u' ) haveVowels = true ; else haveConsonants = true ; // Both the type of letter are present // then increase the ans count if (haveVowels == true && haveConsonants == true ) { ans += 1; haveVowels = false ; haveConsonants = false ; } } // Return the main ans return ans; } // Driver code let S = "happybirthday" ; // Function Call let ans = strengthOfString(S); document.write(ans); // This code is contributed by code_hunt. </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us