Count Vowel Substrings of a String

Difficulty: Easy | Acceptance: 73.10% | Paid: No Topics: Hash Table, String

A vowel substring is a substring of a string that contains only vowels (a, e, i, o, u) and contains all five vowels at least once. Given a string word, return the number of vowel substrings in word.

• Examples
• Constraints
• Brute Force
• Optimized Enumeration

Examples

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (bolded):
- "aeiouu"
- "a**eiou**u"
- "ae**iouu**"
- "aei**ouu**"
- "aeio**uu**"
- "aeiou**u**"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows:
- "cua**ieuoua**c"
- "cua**ieuouac**"
- "cuai**euoua**c"
- "cuai**euouac**"
- "cuaie**uoua**c"
- "cuaie**uouac**"
- "cuaieu**oua**c"
- "cuaieu**ouac**"
- "cuaieuo**ua**c"
- "cuaieuo**uac**"
- "cuaieuou**ac**"
- "cuaieuoua**c**"

Constraints

1 <= word.length <= 100
word consists of lowercase English letters.

Brute Force

Intuition We can generate every possible substring of the input string and check if it meets the criteria: it must contain only vowels and it must contain all five vowels.

Steps

• Initialize a counter to 0.
• Iterate through the string with a start index i from 0 to n-1.
• Iterate through the string with an end index j from i+1 to n.
• Extract the substring word[i:j].
• Check if the set of characters in the substring is exactly equal to the set of all vowels {"a","e","i","o","u"}. This ensures the substring contains only vowels and contains all of them.
• If the condition is met, increment the counter.
• Return the counter.

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        vowels = set('aeiou')
        n = len(word)
        count = 0
        for i in range(n):
            for j in range(i + 1, n + 1):
                sub = word[i:j]
                if set(sub) == vowels:
                    count += 1
        return count

Complexity

• Time: O(n³) - Generating all substrings takes O(n²), and checking validity takes O(n) in the worst case.
• Space: O(1) - We use a fixed set for vowels and a temporary set for the substring characters.
• Notes: Simple to implement but inefficient for very large strings (though n <= 100 here).

Optimized Enumeration

Intuition Instead of generating substrings explicitly, we can iterate through the string and expand valid vowel windows. We maintain a set of vowels seen in the current window. If we encounter a consonant, the window breaks. If the set size reaches 5, we have found a valid substring.

Steps

• Initialize a counter to 0.
• Iterate through the string with a start index i from 0 to n-1.
• Initialize an empty set seen to track vowels in the current window.
• Iterate with an end index j from i to n-1.
• If word[j] is not a vowel, break the inner loop (as substrings must contain only vowels).
• Add word[j] to the seen set.
• If the size of seen is 5, it means we have found a substring containing all five vowels. Increment the counter.
• Return the total count.

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        vowels = set('aeiou')
        n = len(word)
        count = 0
        for i in range(n):
            seen = set()
            for j in range(i, n):
                if word[j] not in vowels:
                    break
                seen.add(word[j])
                if len(seen) == 5:
                    count += 1
        return count

Complexity

• Time: O(n²) - We use two nested loops, but operations inside are O(1).
• Space: O(1) - The seen set stores at most 5 characters.
• Notes: This is the optimal approach for this problem given the constraints, avoiding the overhead of substring creation.