A substring is a contiguous (non-empty) sequence of characters within a string.
A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.
Given a string word, return the number of vowel substrings in word.
Example 1:
Input: word = "aeiouu" Output: 2 Explanation: The vowel substrings of word are as follows (underlined): - "aeiouu" - "aeiouu"
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 (underlined): - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac" - "cuaieuouac"
Constraints:
1 <= word.length <= 100word consists of lowercase English letters only.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(n2), 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.
This approach involves iterating over all possible substrings of the given string and checking if each substring contains all the vowels ('a', 'e', 'i', 'o', 'u'). This is a straightforward method but not optimized due to the nested loop structure.
The solution in C involves two nested loops to iterate over all possible substrings. Each substring is then checked for the presence of all five vowels using the helper function 'containsAllVowels'. The 'isVowel' function helps in determining if a character is part of the vowels.
Time Complexity: O(n^3) due to the triply nested loop structure.
Space Complexity: O(1) as only a fixed-size array is used to check vowels.
This approach leverages a sliding window mechanism to efficiently find substrings containing all vowels. By keeping track of the vowel count, the window can be expanded and contracted to find matches, significantly reducing unnecessary duplicate work.
The C implementation uses a sliding window to efficiently manage the range in which all vowels appear. When a non-vowel is encountered, the state is reset, improving performance over analyzing static substrings.
Time Complexity: O(n) compared to the traditional O(n^3).
Space Complexity: O(1).
We can enumerate the left endpoint i of the substring. For the current left endpoint, maintain a hash table to record the vowels that appear in the current substring. Then enumerate the right endpoint j. If the character at the current right endpoint is not a vowel, break the loop. Otherwise, add the character at the current right endpoint to the hash table. If the number of elements in the hash table is 5, it means the current substring is a vowel substring, and increment the result by 1.
The time complexity is O(n^2), and the space complexity is O(C). Here, n is the length of the string word, and C is the size of the character set, which is 5 in this problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) due to the triply nested loop structure. |
| Sliding Window Approach | Time Complexity: O(n) compared to the traditional O(n^3). |
| Brute Force Enumeration + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem and verifying logic on small inputs |
| Sliding Window with Vowel Frequency | O(n) | O(1) | Preferred solution for large strings and typical interview expectations |
2062. Count Vowel Substrings of a String (Leetcode Easy) • Programming Live with Larry • 4,266 views views
Watch 9 more video solutions →Practice Count Vowel Substrings of a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor