Last Updated: 1 Apr, 2021
Count Of Substrings Consisting Only Of Vowels
Easy
Asked in companies
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’}.
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
Approaches
- 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.
- The idea here is to count the length of the substring that contains only vowels.
- For a length of ‘y’, the possible substrings which contain only vowels are (y * (y + 1)) / 2. We’ll repeat this process for every such substring.
- Create a variable named ans to store the final answer, and initialize it with 0.
- Create one more variable named y, that will contain the length of the substring, initialize it with 0.
- Run a loop from i = 0 to i < |S|, in each iteration do:
- If S[i] is a vowel, then increment y by 1.
- Else:
- Add (y * (y + 1)) / 2 to the ans.
- Set y to 0.
- If y != 0, then we have to add the remaining substring into the ans, i.e., add (y * (y + 1)) / 2 to the ans.
- Return the ans.