Substrings starting with vowel and ending with consonants and vice versa
Given a string s, count special substrings in it. A Substring of S is said to be special if either of the following properties is satisfied.
- It starts with a vowel and ends with a consonant.
- It starts with a consonant and ends with a vowel.
Examples:
Input : S = "aba" Output : 2 Substrings of S are : a, ab, aba, b, ba, a Out of these only 'ab' and 'ba' satisfy the condition for special Substring. So the answer is 2. Input : S = "adceba" Output : 9
A simple solution is to generate all substrings. For every substring check the condition of special string. If yes increment count.
An efficient solution is to count vowels and consonants in every suffix of string. After counting these, we traverse string from beginning. For every consonant, we add number of vowels after it to result. Similarly, for every vowel, we add number of consonants after it.
C++
// CPP program to count special strings #include <bits/stdc++.h> using namespace std; // Returns true if ch is vowel bool isVowel( char ch) { return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ); } // function to check consonant bool isCons( char ch) { return (ch != 'a' && ch != 'e' && ch != 'i' && ch != 'o' && ch != 'u' ); } int countSpecial(string &str) { int len = str.length(); //in case of empty string, we can't fulfill the //required condition, hence we return ans as 0. if (len == 0) return 0; // co[i] is going to store counts // of consonants from str[len-1] // to str[i]. // vo[i] is going to store counts // of vowels from str[len-1] // to str[i]. int co[len + 1]; int vo[len + 1]; memset (co, 0, sizeof (co)); memset (vo, 0, sizeof (vo)); // Counting consonants and vowels // from end of string. if (isCons(str[len - 1]) == 1) co[len-1] = 1; else vo[len-1] = 1; for ( int i = len-2; i >= 0; i--) { if (isCons(str[i]) == 1) { co[i] = co[i + 1] + 1; vo[i] = vo[i + 1]; } else { co[i] = co[i + 1]; vo[i] = vo[i + 1] + 1; } } // Now we traverse string from beginning long long ans = 0; for ( int i = 0; i < len; i++) { // If vowel, then count of substrings // starting with str[i] is equal to // count of consonants after it. if (isVowel(str[i])) ans = ans + co[i + 1]; // If consonant, then count of // substrings starting with str[i] // is equal to count of vowels // after it. else ans = ans + vo[i + 1]; } return ans; } // driver program int main() { string str = "adceba" ; cout << countSpecial(str); return 0; } |
Java
// Java program to count special strings class GfG { // Returns true if ch is vowel static boolean isVowel( char ch) { return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ); } // function to check consonant static boolean isCons( char ch) { return (ch != 'a' && ch != 'e' && ch != 'i' && ch != 'o' && ch != 'u' ); } static int countSpecial( char []str) { int len = str.length; //in case of empty string, we can't fulfill the //required condition, hence we return ans as 0. if (len == 0 ) return 0 ; // co[i] is going to store counts // of consonants from str[len-1] // to str[i]. // vo[i] is going to store counts // of vowels from str[len-1] // to str[i]. int co[] = new int [len + 1 ]; int vo[] = new int [len + 1 ]; // Counting consonants and vowels // from end of string. if (isCons(str[len - 1 ]) == true ) co[len- 1 ] = 1 ; else vo[len- 1 ] = 1 ; for ( int i = len- 2 ; i >= 0 ; i--) { if (isCons(str[i]) == true ) { co[i] = co[i + 1 ] + 1 ; vo[i] = vo[i + 1 ]; } else { co[i] = co[i + 1 ]; vo[i] = vo[i + 1 ] + 1 ; } } // Now we traverse string from beginning long ans = 0 ; for ( int i = 0 ; i < len; i++) { // If vowel, then count of substrings // starting with str[i] is equal to // count of consonants after it. if (isVowel(str[i])) ans = ans + co[i + 1 ]; // If consonant, then count of // substrings starting with str[i] // is equal to count of vowels // after it. else ans = ans + vo[i + 1 ]; } return ( int ) ans; } // Driver program public static void main(String[] args) { String str = "adceba" ; System.out.println(countSpecial(str.toCharArray())); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program to count special strings # Returns true if ch is vowel def isVowel(ch): return (ch = = 'a' or ch = = 'e' or ch = = 'i' or ch = = 'o' or ch = = 'u' ) # Function to check consonant def isCons( ch): return (ch ! = 'a' and ch ! = 'e' and ch ! = 'i' and ch ! = 'o' and ch ! = 'u' ) def countSpecial( str ): lent = len ( str ) #in case of empty string, we can't fulfill the #required condition, hence we return ans as 0. if lent = = 0 : return 0 ; # co[i] is going to store counts # of consonants from str[len-1] # to str[i]. # vo[i] is going to store counts # of vowels from str[len-1] # to str[i]. co = [] vo = [] for i in range ( 0 , lent + 1 ): co.append( 0 ) for i in range ( 0 , lent + 1 ): vo.append( 0 ) # Counting consonants and vowels # from end of string. if isCons( str [lent - 1 ]) = = 1 : co[lent - 1 ] = 1 else : vo[lent - 1 ] = 1 for i in range (lent - 2 , - 1 , - 1 ): if isCons( str [i]) = = 1 : co[i] = co[i + 1 ] + 1 vo[i] = vo[i + 1 ] else : co[i] = co[i + 1 ] vo[i] = vo[i + 1 ] + 1 # Now we traverse string from beginning ans = 0 for i in range (lent): #If vowel, then count of substrings # starting with str[i] is equal to # count of consonants after it. if isVowel( str [i]): ans = ans + co[i + 1 ] #If consonant, then count of # substrings starting with str[i] # is equal to count of vowels # after it. else : ans = ans + vo[i + 1 ] return ans # Driver Code str = "adceba" print (countSpecial( str )) # This code is contributed by Upendra singh bartwal |
C#
// C# program to count special strings using System; class GFG { // Returns true if ch is vowel static Boolean isVowel( char ch) { return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ); } // function to check consonant static Boolean isCons( char ch) { return (ch != 'a' && ch != 'e' && ch != 'i' && ch != 'o' && ch != 'u' ); } static int countSpecial( char []str) { int len = str.Length; //in case of empty string, we can't fulfill the //required condition, hence we return ans as 0. if (len == 0) return 0; // co[i] is going to store counts // of consonants from str[len-1] // to str[i]. // vo[i] is going to store counts // of vowels from str[len-1] // to str[i]. int []co = new int [len + 1]; int []vo = new int [len + 1]; // Counting consonants and vowels // from end of string. if (isCons(str[len - 1]) == true ) co[len - 1] = 1; else vo[len - 1] = 1; for ( int i = len - 2; i >= 0; i--) { if (isCons(str[i]) == true ) { co[i] = co[i + 1] + 1; vo[i] = vo[i + 1]; } else { co[i] = co[i + 1]; vo[i] = vo[i + 1] + 1; } } // Now we traverse string from beginning long ans = 0; for ( int i = 0; i < len; i++) { // If vowel, then count of substrings // starting with str[i] is equal to // count of consonants after it. if (isVowel(str[i])) ans = ans + co[i + 1]; // If consonant, then count of // substrings starting with str[i] // is equal to count of vowels // after it. else ans = ans + vo[i + 1]; } return ( int ) ans; } // Driver program public static void Main(String[] args) { String str = "adceba" ; Console.WriteLine(countSpecial(str.ToCharArray())); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to count special strings // Returns true if ch is vowel function isVowel(ch) { return (ch === "a" || ch === "e" || ch === "i" || ch === "o" || ch === "u" ); } // Function to check consonant function isCons(ch) { return (ch !== "a" && ch !== "e" && ch !== "i" && ch !== "o" && ch !== "u" ); } function countSpecial(str) { var len = str.length; //in case of empty string, we can't fulfill the //required condition, hence we return ans as 0. if (len == 0) return 0; // co[i] is going to store counts // of consonants from str[len-1] // to str[i]. // vo[i] is going to store counts // of vowels from str[len-1] // to str[i]. var co = new Array(len + 1).fill(0); var vo = new Array(len + 1).fill(0); // Counting consonants and vowels // from end of string. if (isCons(str[len - 1]) === true ) co[len - 1] = 1; else vo[len - 1] = 1; for ( var i = len - 2; i >= 0; i--) { if (isCons(str[i]) === true ) { co[i] = co[i + 1] + 1; vo[i] = vo[i + 1]; } else { co[i] = co[i + 1]; vo[i] = vo[i + 1] + 1; } } // Now we traverse string from beginning var ans = 0; for ( var i = 0; i < len; i++) { // If vowel, then count of substrings // starting with str[i] is equal to // count of consonants after it. if (isVowel(str[i])) ans = ans + co[i + 1]; // If consonant, then count of // substrings starting with str[i] // is equal to count of vowels // after it. else ans = ans + vo[i + 1]; } return parseInt(ans); } // Driver code var str = "adceba" ; document.write(countSpecial(str.split( "" ))); // This code is contributed by rdtank </script> |
9
Time Complexity : O( |str| ) , as we make a linear traversal to count the number of vowels and consonants.
Space Complexity for above solution : O( |str| ), as we make two arrays vo[] and co[] to store the number of vowels at any index i.
The above solution can be optimized to be done in O(1) space complexity, by using only two variables instead of making two arrays to store vowels and consonants at any index i. Following code depicts the same :
C++
#include <bits/stdc++.h> using namespace std; // function to check if a character is vowel or not bool isVowel( char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) return true ; return false ; } long long countSpecial(string str) { long long cnt = 0; int n = str.size(); // in case of single character or empty string // we can't fulfill the given condition , hence the // count is 0. if (n == 1 || n == 0) return 0; // variables to store count of total vowels and // consonants in the string long long vow = 0, cons = 0; for ( int i = 0; i < n; i++) vow += isVowel(str[i]); cons = n - vow; for ( int i = 0; i < n; i++) { // as we encounter a vowel, we add no. of consonants // after it to our answer and decrease the value of // vow by 1, indicating that now the remaining // string has one vowel less than current string if (isVowel(str[i])) { vow--; cnt += cons; } // same case as above for consonants else { cons--; cnt += vow; } } // finally we return the cnt as our answer return cnt; } int main() { string str = "adceba" ; cout << countSpecial(str); return 0; } |
C
#include <stdio.h> // function to check if a character is vowel or not int isVowel( char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) return 1; return 0; } long long countSpecial( char str[], int n) { long long cnt = 0; // in case of single character or empty string // we can't fulfill the given condition , hence the // count is 0. if (n == 1 || n == 0) return 0; // variables to store count of total vowels and // consonants in the string long long vow = 0, cons = 0; for ( int i = 0; i < n; i++) vow += isVowel(str[i]); cons = n - vow; for ( int i = 0; i < n; i++) { // as we encounter a vowel, we add no. of consonants // after it to our answer and decrease the value of // vow by 1, indicating that now the remaining // string has one vowel less than current string if (isVowel(str[i])) { vow--; cnt += cons; } // same case as above for consonants else { cons--; cnt += vow; } } // finally we return the cnt as our answer return cnt; } int main() { char str[] = { 'a' , 'd' , 'c' , 'e' , 'b' , 'a' }; int n = sizeof (str) / sizeof ( char ); if (n == 0) { printf ( "0" ); } else { long long count = countSpecial(str, n); printf ( "%lld" , count); } return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // function to check if a character is vowel or not public static int isVowel( char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) return 1 ; return 0 ; } public static long countSpecial(String str) { long cnt = 0 ; int n = str.length(); // in case of single character or empty string // we can't fulfill the given condition , hence the // count is 0. if (n == 1 || n == 0 ) return 0 ; // variables to store count of total vowels and // consonants in the string long vow = 0 , cons = 0 ; for ( int i = 0 ; i < n; i++) { char ch = str.charAt(i); vow += isVowel(ch); } cons = n - vow; for ( int i = 0 ; i < n; i++) { char ch = str.charAt(i); // as we encounter a vowel, we add no. of // consonants after it to our answer // and decrease the value of vow by 1, // indicating that now the remaining // string has one vowel less than current string if (isVowel(ch) == 1 ) { vow--; cnt += cons; } // same case as above for consonants else { cons--; cnt += vow; } } // finally we return the cnt as our answer return cnt; } public static void main(String[] args) { String str = "adceba" ; long count = countSpecial(str); System.out.println(count); } } |
Python3
'''package whatever #do not write package name here ''' # function to check if a character is vowel or not def isVowel(ch): if (ch = = 'a' or ch = = 'e' or ch = = 'i' or ch = = 'o' or ch = = 'u' ): return 1 ; return 0 ; def countSpecial( str ): cnt = 0 ; n = len ( str ); # in case of single character or empty string # we can't fulfill the given condition , hence the # count is 0. if (n = = 1 or n = = 0 ): return 0 ; # variables to store count of total vowels and # consonants in the string vow = 0 cons = 0 ; for i in range (n): ch = str [i]; vow + = isVowel(ch); cons = n - vow; for i in range (n): ch = str [i]; # as we encounter a vowel, we add no. of # consonants after it to our answer # and decrease the value of vow by 1, # indicating that now the remaining # string has one vowel less than current string if (isVowel(ch) = = 1 ): vow - = 1 ; cnt + = cons; # same case as above for consonants else : cons - = 1 ; cnt + = vow; # finally we return the cnt as our answer return cnt; # Driver code if __name__ = = '__main__' : str = "adceba" ; count = countSpecial( str ); print (count); # This code is contributed by Rajput-Ji |
C#
/*package whatever //do not write package name here */ using System; class GFG { // function to check if a character is vowel or not public static int isVowel( char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) return 1; return 0; } public static long countSpecial(String str) { long cnt = 0; int n = str.Length; // in case of single character or empty string // we can't fulfill the given condition , hence the // count is 0. if (n == 1 || n == 0) return 0; // variables to store count of total vowels and // consonants in the string long vow = 0, cons = 0; for ( int i = 0; i < n; i++) { char ch = str[i]; vow += isVowel(ch); } cons = n - vow; for ( int i = 0; i < n; i++) { char ch = str[i]; // as we encounter a vowel, we add no. of // consonants after it to our answer // and decrease the value of vow by 1, // indicating that now the remaining // string has one vowel less than current string if (isVowel(ch) == 1) { vow--; cnt += cons; } // same case as above for consonants else { cons--; cnt += vow; } } // finally we return the cnt as our answer return cnt; } // Driver code public static void Main(String[] args) { string str = "adceba" ; long count = countSpecial(str); Console.Write(count); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> /*package whatever //do not write package name here */ // function to check if a character is vowel or not function isVowel(ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ) return 1; return 0; } function countSpecial(str) { var cnt = 0; var n = str.length; // in case of single character or empty string // we can't fulfill the given condition , hence the // count is 0. if (n == 1 || n == 0) return 0; // variables to store count of total vowels and // consonants in the string var vow = 0, cons = 0; for ( var i = 0; i < n; i++) { var ch = str.charAt(i); vow += isVowel(ch); } cons = n - vow; for ( var i = 0; i < n; i++) { var ch = str.charAt(i); // as we encounter a vowel, we add no. of // consonants after it to our answer // and decrease the value of vow by 1, // indicating that now the remaining // string has one vowel less than current string if (isVowel(ch) == 1) { vow--; cnt += cons; } // same case as above for consonants else { cons--; cnt += vow; } } // finally we return the cnt as our answer return cnt; } var str = "adceba" ; var count = countSpecial(str); document.write(count); // This code is contributed by shivanisinghss2110 </script> |
9
Time Complexity : O( |str| )
Space Complexity : O(1)