Count Vowel Substrings of a String - Video Solutions

Problem Overview: You are given a string and need to count substrings that contain only vowels (a, e, i, o, u) and include all five vowels at least once. Any substring containing a consonant is invalid, so valid substrings must be continuous vowel segments that contain the full vowel set.

Approach 1: Brute Force Enumeration (Time: O(n²), Space: O(1))

Iterate over every possible starting index and expand the substring one character at a time. While expanding, stop immediately if you hit a consonant because the substring can no longer be valid. Track vowels using a small frequency array or a hash set. Whenever the set size becomes five, the current substring contains all vowels and contributes to the count. This approach is straightforward and helps verify correctness, but it checks many overlapping substrings.

The key observation is that valid substrings must be entirely composed of vowels. As soon as a consonant appears, the expansion stops and the next starting index is tested. Even though the logic is simple, nested iteration makes the runtime quadratic in the worst case when the string contains long vowel segments.

Approach 2: Sliding Window with Vowel Frequency (Time: O(n), Space: O(1))

The optimal solution scans the string using a sliding window. Maintain two pointers that define a window containing only vowels. Use a small frequency map (or array indexed by vowel) to track how many of each vowel appears in the current window. If a consonant appears, reset the window because valid substrings cannot cross consonants.

As the window expands, update the vowel counts and track how many distinct vowels are present. When all five vowels exist in the window, every valid prefix of the window also forms a valid substring. By adjusting the left pointer while maintaining the vowel requirement, you can count multiple substrings efficiently. Each character enters and leaves the window at most once, giving linear time complexity.

This technique is a common pattern for substring counting problems involving constraints on characters. It relies on constant‑size tracking structures and pointer movement rather than repeatedly rebuilding substrings.

Recommended for interviews: Start by describing the brute force substring enumeration to demonstrate understanding of the constraints. Then move to the optimized sliding window solution. Interviewers typically expect the linear scan because it shows familiarity with substring problems involving string processing and character tracking using a hash table or frequency array.