Count Of Substrings Consisting Only Of Vowels

Easy
0/40
Average time to solve is 20m
profile
Contributed by
18 upvotes
Asked in companies
FacebookExpedia GroupDunzo

Problem statement

You are a string ‘S’. Your task is to count all the “substrings” of ‘S’ that contain only “vowels”.

Note : 
1. The string ‘S’ consists of only lowercase English alphabets.
2. A ‘substring’ is a contiguous sequence of characters within a string.
3. Recall that vowels in lowercase English alphabets are: {‘a’, ‘e’, ‘i’, ‘o’, ‘u’}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow. 

The first and only line of each test case contains a string ‘S’ of lowercase letters.
Output Format : 
For each test case, print in a new line an integer denoting the number of all “substrings” of ‘S’ that contain only “vowels”.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= |S| <= 5000

Time Limit: 1sec
Sample Input 1 :
2
codestudio
wxyz
Sample Output 1 :
6
0
Explanation For Sample Input 1 :
Test Case 1 :
The substrings that contain only vowels are: {“o”, “e”, “u”, “i”, “io”, “o”}. 

Test Case 2 :
There is no substring that contains only vowels.
Sample Input 2 :
2
codingninjas
artycg
Sample Output 2 :
4
1
Hint

Think of generating all substrings, and check each individually.

Approaches (2)
Brute Force Approach
  • The idea here is to generate all substrings and check each individually, whether they contain only vowels or not.
  • Create a variable named ans to store the final answer, and initialize it with 0.
  • Run a loop from i = 0 to i < |S|, in each iteration do:
    • Create an empty string named sub, which is going to contain the current substring starting from the ith character.
    • Again run a loop from j = i to j < |S|, in each iteration do:
      • Add S[j] into the string sub.
      • If sub only contains vowel, then increment ans by 1. To check whether the string sub is valid or not we can call a function check and pass the string sub. This function will return true if the string sub is valid. Otherwise, it will return false.
  • Return the ans.

 

bool check(string sub):

 

  • This function is checking whether our substring sub is valid or not.
  • Run a loop from i = 0 to i < |sub|, in each iteration do:
    • If sub[i] is not a vowel, then return false.
  • If the loop terminates, then the string sub must contain only the vowels. So, we have to return true.
Time Complexity

O(N^3), where ‘N’ is the size of the input string.

 

To generate all substrings, the time complexity will be O(N^2). After generating a particular substring we are checking whether it contains only vowels or not, which take O(N) more for each time. Hence, the overall time complexity will be O(N^3).

Space Complexity

O(N), where ‘N’ is the size of the input string.


As we are generating the substring in the new variable which is of data type string. The size of this string can go up to ‘N’. Hence, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Count Of Substrings Consisting Only Of Vowels
Full screen
Console