Solution For Count Vowel Substrings Of A String

Problem Statement

Given a string s, return the number of substrings that consist of vowels only.

A substring is a contiguous sequence of characters within a string.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

Example:

Input: s = “abc”
Output: 0

Input: s = “aeiou”
Output: 15

Solution

Approach:

To solve this problem, we can follow the below steps:

• Initialize a variable ans to store the result, which will be the count of all substrings having only vowels.
• Initialize two variables i and j to track the indices of the leftmost and rightmost vowels present in the string, respectively.

• Traverse the string s and for each character:

• If the character is a vowel, update j to its index. If j increases, then all the substrings starting from i till j will be valid vowel substrings. We can add (j-i+1) to our existing ans value as it will give the count of all substrings that end at or after j.

• If the character is not a vowel, update i to j+1 and reset j to the previous index of vowel found in the string. This is because all the substrings that end before j are invalid since they do not have a vowel.

• Return the final answer stored in ans.

Let’s see the implementation of the above approach:

class Solution {
public:
int countVowelStrings(string s) {
int ans = 0, i = -1, j = -1;
for (char c : s) {
if (c == ‘a’ || c == ‘e’ || c == ‘i’ || c == ‘o’ || c == ‘u’) {
j = s.find_last_of(c); // update j to the rightmost index of vowel c in the string
ans += (j-i); // add substrings that end at or after j and start at or after i
} else {
i = j+1; // set i to the index after j
j = s.find_last_of(“aeiou”,j); // set j to the previous index of vowel found in the string
}
}
return ans;
}
};

Time Complexity:

• The time complexity of the above approach is O(N), where N is the length of the input string s.

Space Complexity:

• The space complexity of the above approach is O(1), as we are not using any extra space.

Step by Step Implementation For Count Vowel Substrings Of A String

int countVowelSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                if (isValid(sub)) {
                    count++;
                }
            }
        }
        return count;
    }
    
    boolean isValid(String sub) {
        int[] vowels = new int[5];
        for (char c : sub.toCharArray()) {
            if (c == 'a') {
                vowels[0]++;
            } else if (c == 'e') {
                vowels[1]++;
            } else if (c == 'i') {
                vowels[2]++;
            } else if (c == 'o') {
                vowels[3]++;
            } else if (c == 'u') {
                vowels[4]++;
            }
        }
        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                if (vowels[i] > vowels[j]) {
                    return false;
                }
            }
        }
        return true;
    }

def countVowelSubstrings(s): 

# Initialize result 

count = 0

# Consider all substrings and increment 

# count of substrings starting 

# with a vowel 

for i in range(len(s)): 

for j in range(i, len(s)): 

if (isVowel(s[i])): 

count += 1

return count 

# A utility function to check whether 

# a character is vowel 

def isVowel(c): 

c = c.lower() 

if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'): 

return True

return False

var countVowelSubstrings = function(s) {
    // create a hashmap to store the count of each vowel
    let hashmap = {};
    hashmap['a'] = 0;
    hashmap['e'] = 0;
    hashmap['i'] = 0;
    hashmap['o'] = 0;
    hashmap['u'] = 0;
    
    // create a variable to store the final count
    let count = 0;
    
    // loop through the string
    for(let i = 0; i < s.length; i++){
        // if the character is a vowel, increment the count for that vowel in the hashmap
        if(s[i] == 'a'){
            hashmap['a']++;
        } else if(s[i] == 'e'){
            hashmap['e']++;
        } else if(s[i] == 'i'){
            hashmap['i']++;
        } else if(s[i] == 'o'){
            hashmap['o']++;
        } else if(s[i] == 'u'){
            hashmap['u']++;
        }
        
        // for each vowel in the hashmap, add the number of substrings that can be formed with that vowel to the final count
        count += hashmap['a'];
        count += hashmap['e'];
        count += hashmap['i'];
        count += hashmap['o'];
        count += hashmap['u'];
    }
    
    return count;
};

int countVowelSubstrings(string s) 
{ 
    // a, e, i, o, u 
    int n = s.length(); 
  
    // dp[i][j] stores the count of 
    // substrings ending with 
    // vowel s[i] and starting 
    // with vowel s[j] 
    int dp[5][5] = { { 0 } }; 
  
    // Initialize the count 
    int ans = 0; 
  
    // loop for length of string 
    for (int i = 0; i < n; i++) { 
  
        // loop for vowel 
        for (int j = 0; j < 5; j++) { 
  
            // loop for vowel 
            for (int k = 0; k < 5; k++) { 
  
                // If the current substrings 
                // ends with vowel s[i] 
                // and starts with vowel s[j] 
                if (s[i] == 'a' + j) { 
                    dp[j][k]++; 
                    ans += dp[j][k]; 
                } 
            } 
        } 
    } 
  
    return ans; 
}

int CountVowelSubstrings(string s) 
        { 
            // creating an array of the vowels 
            char[] vowel = { 'a', 'e', 'i', 'o', 'u' }; 
  
            // stores the count of substrings 
            int count = 0; 
  
            for (int i = 0; i < s.Length; i++) 
            { 
                // if the current character is vowel 
                if (vowel.Contains(s[i])) 
                { 
                    // stores the count of substrings 
                    // ending with the current character 
                    int temp = 1; 
  
                    // loop from the current character 
                    // to the end of the string 
                    for (int j = i + 1; j < s.Length; j++) 
                    { 
                        // if the character is vowel 
                        if (vowel.Contains(s[j])) 
                            temp++; 
                        else
                            break; 
                    } 
  
                    // adding the temp to the count 
                    count += temp; 
                } 
            } 
            return count; 
        }