Count Vowel Substrings of a String

Count Vowel Substrings of a String

What is this problem about?

The Count Vowel Substrings of a String interview question asks you to count all substrings that consist only of vowels and contain at least one of every vowel ('a', 'e', 'i', 'o', and 'u'). This means any consonant in a substring makes it invalid, and a substring of only vowels is only valid if it isn't missing any of the five required characters.

Why is this asked in interviews?

Companies like Amazon and Oracle use this string interview question to test your ability to handle sliding window or two-pointer logic with specific character constraints. It evaluates how you manage a "vowel-only" window and how you efficiently track the frequency of distinct characters within that window.

Algorithmic pattern used

This problem can be solved using a Sliding Window or Hash Table approach.

1. Iterate through the string.
2. For each starting position, expand a window as long as you encounter vowels.
3. Use a Hash Map or frequency array to track the counts of 'a', 'e', 'i', 'o', 'u'.
4. If the number of distinct vowels in the current window is 5, increment the count.
5. If a consonant is hit, the current window is terminated.

Example explanation

String: s = "aeiouu"

• Substring "aeio" -> Missing 'u'. (Invalid)
• Substring "aeiou" -> Has all five. (Valid!)
• Substring "aeiouu" -> Consists only of vowels and has all five. (Valid!)
• Substring "eiouu" -> Missing 'a'. (Invalid) Total valid substrings starting at index 0: 2.

Common mistakes candidates make

• Ignoring the "All Vowels" Rule: Counting substrings that have only vowels but are missing one (e.g., "aeio").
• Consonant Handling: Not resetting the search or the vowel frequency map when a consonant is encountered.
• Efficiency: Using O(n^3) by generating all substrings and checking each one, rather than an optimized sliding window approach.

Interview preparation tip

A useful trick for "exactly K distinct elements" or "at least K distinct elements" is to solve for "at most K" and "at most K-1" and subtract them. For this problem, you can also filter the string into vowel-only blocks and solve each block independently.