Vowel and Consonant Substrings! - InterviewBit Solution

Problem: Vowel and Consonant Substrings!

Problem Description

Given a string A consisting of lowercase characters. You have to find the number of substrings in A which starts with vowel and end with consonants or vice-versa. Return the count of substring modulo 109 + 7.

Problem Constraints

1 <= |A| <= 105 A consists only of lower-case characters.

Input Format

First argument is an string A.

Output Format

Return a integer denoting the number of substrings in A which starts with vowel and end with consonants or vice-versa with modulo 109 + 7.

Example Input

Input 1: A = "aba" Input 2: A = "a"

Example Output

Output 1: 2 Output 2: 0

Example Explanation:

Explanation 1:

 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.

Explanation 2:

 No possible substring that start with vowel and end with consonant or vice-versa.

Solution Approach:

To count the substring starting with a vowel and ending with consonants, start counting consonants from backwards and whenever you encounter a vowel add the count of consonants so far to the answer.

For example, take

A = "ababb"

# Count Strings starting with vowel and ending with consonant.

let, i=4 -> current index (len(A) - 1)
   , cnt=0 -> store the number of consonents visited
   , ans=0 -> end result

i=4: A[4] = b // consonant
   => cnt = 1, ans = 0
   
i=3: A[3] = b // consonant
   => cnt = 2, ans = 0 

i=2: A[2] = a // vowel 
   => cnt = 2, ans = 2 ->(ans + cnt = 0 + 2)
Reason: Because with current vowel you can make cnt no. of string
    
i=1: A[1] = b // consonant 
   => cnt = 3, ans = 2 

i=0: A[0] = a // vowel 
   => cnt = 3, ans = 5 ->(ans + cnt = 2 + 3)
Reason: Because with current vowel you can make cnt no. of string

Similarly, do the reverse for counting the string starting from consonants and ending with a vowel.

A = "ababb"
# Count Strings starting with consonant and ending with vowel.

let, i=4 -> current index (len(A) - 1)
   , cnt=0 -> store the number of vowel visited
   , ans1=0 -> end result
   
i=4: A[4] = b // consonant
   => cnt = 0, ans1 = 0
   
i=3: A[3] = b // consonant
   => cnt = 0, ans1 = 0 

i=2: A[2] = a // vowel 
   => cnt = 1, ans1 = 0
    
i=1: A[1] = b // consonant 
   => cnt = 1, ans1 = 1 ->(ans1 = ans1 + cnt = 0 + 1) 
Reason:Because with current consonant you can make cnt no.of string

i=0: A[0] = a // vowel 
   => cnt = 2, ans1 = 1

Result: ans + ans1 = 5 + 1 = 6

Time & Space Complexity:

Time Complexity: O(N)

Space Complexity: O(N)

Solution:

Code in C++

If you have any questions or queries, feel free to drop a comment in the comments section below.

Note: Help us improve this blog

If you have a better solution, and you think you can help your peers to understand this problem better, then please drop your solution and approach in the comments section below.

We will upload your approach and solution here by giving you the proper credit so that you can showcase it among your peers.