2062. Count Vowel Substrings of a String
Asked at Salesforce, Snowflake, DE Shaw
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Hash Table
Companies
3
Problem
You are given a string word. A vowel substring is a contiguous, non-empty piece of word that (1) contains only vowels — the letters a, e, i, o, u — and (2) contains all five of those vowels at least once.
Return the number of vowel substrings in word. Count each starting and ending position pair separately, even if the resulting text looks the same as another one.
Note that any substring containing a consonant is never valid, so you can stop scanning as soon as you hit one.
What counts as a vowel substring
Constraints
- ●
1 <= word.length <= 100 - ●
word consists of lowercase English letters only.
Examples
word = "aeiouu"2word = "unicornarihan"0word = "cuaieuouac"7Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Salesforce | Easy | View all Salesforce questions → |
| Snowflake | Easy | View all Snowflake questions → |
| DE Shaw | Easy | View all DE Shaw questions → |
How to Think About It
Brute force: generate every possible substring and check if it contains all 5 vowels. For a string of length n, there are n*(n+1)/2 substrings. Checking each takes O(n). Total: O(n³). Works for small inputs.
Optimized brute force: for each starting index i, extend the ending index j and maintain a set of vowels seen. When the set has 5 vowels, all substrings starting at i and ending at j or beyond are valid (until the next non-vowel or end). This is O(n²) in the worst case.
Key observation: count all substrings that contain at least all 5 vowels = (count of substrings with at least all 5 vowels starting from each position). For each start i, find the first j where word[i:j+1] has all 5 vowels. Then n - j substrings starting at i are valid.
Sliding window approach: maintain a window with a Counter of vowels. Expand right. When the window has all 5 vowels, count how many valid substrings end at the current position. Shrink from left when possible to avoid overcounting.
Even simpler: count substrings with all vowels = total substrings with all vowels - substrings missing at least one vowel. Use inclusion-exclusion: for each vowel, count substrings that do NOT contain it. Subtract from total. But this is complex for 5 vowels.
Practical approach: use a nested loop with early termination. For each start i, walk forward until you have all 5 vowels. Count n - last_valid_end for that start. This is O(n * 5) = O(n) amortized since each character is visited once per start.
Optimal Approach
For each starting index i, find the smallest ending index j >= i such that word[i:j+1] contains all 5 vowels. If found, all substrings starting at i and ending at j, j+1, ..., n-1 are valid. Count n - j for that i.
Walkthrough with word = "aeiouu":
- i=0: scan from 0. At j=4, we have "aeiou" (all 5 vowels). Count += 6 - 4 = 2. (substrings [0:4], [0:5])
- i=1: scan from 1. At j=4, we have "eiou" (missing a). At j=5, we have "eiouu" (missing a). No valid end. Count += 0.
- i=2: scan from 2. At j=5, we have "iouu" (missing a, e). No valid end. Count += 0.
- i=3: scan from 3. At j=5, "ouu" (missing a, e, i). No valid end. Count += 0.
- i=4: scan from 4. "uu" (missing a, e, i, o). No valid end. Count += 0.
- i=5: "u" (missing most). No valid end. Count += 0.
- Total: 2.
Walkthrough with word = "aabeiioou":
- i=0: at j=8, all vowels appear. Count += 9 - 8 = 1.
- Total: 1.
Time: O(n * 5) = O(n) amortized — each starting index scans forward, but the total scan is bounded by 5n since each vowel type only needs to be found once per window. Space: O(1) — fixed-size vowel set.
For each start, find the first end with all 5 vowels
What Trips People Up in Real Interviews
Confusing "substring" with "subsequence". Substrings are contiguous; subsequences are not. The problem asks for substrings, so you need contiguous character sequences.
Overcounting by not using the "first valid end" optimization. For each starting index, find the FIRST position where all 5 vowels appear. All substrings from that position to the end are valid. Do not iterate beyond the first valid end.
Forgetting that vowels can repeat. "aaeiou" still counts as having all 5 vowels. Your vowel set/counter must track presence, not count.
Not handling strings shorter than 5 characters. A string with fewer than 5 characters cannot contain all 5 vowels. Return 0 immediately.
Missing edge cases with consonants mixed in. "aebcdefgiou" has all vowels starting from index 0 at position 9. Substrings [0:9], [0:10], [0:11] are valid. Consonants between vowels do not break the substring.
Solution Code
O(n) timedef countVowelSubstrings(word):
vowels = set('aeiou')
n = len(word)
count = 0
for i in range(n):
seen = set()
for j in range(i, n):
if word[j] in vowels:
seen.add(word[j])
if len(seen) == 5:
count += n - j
break
else:
break
return countFrequently Asked Questions
What is the Count Vowel Substrings of a String problem?
Given a string `word`, return the number of substrings that contain every vowel (a, e, i, o, u) at least once. A substring is a contiguous sequence of characters. For example, "aeiou" has 1 vowel substring, and "aeiouu" has 2.
How do you solve Count Vowel Substrings of a String?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Vowel Substrings of a String?
Count Vowel Substrings of a String is asked at Salesforce, Snowflake, DE Shaw. It is a easy difficulty problem.
What are common mistakes on Count Vowel Substrings of a String?
- Confusing "substring" with "subsequence". Substrings are contiguous; subsequences are not. The problem asks for substrings, so you need contiguous character sequences.
- Overcounting by not using the "first valid end" optimization. For each starting index, find the FIRST position where all 5 vowels appear. All substrings from that position to the end are valid. Do not iterate beyond the first valid end.
- Forgetting that vowels can repeat. "aaeiou" still counts as having all 5 vowels. Your vowel set/counter must track presence, not count.
- Not handling strings shorter than 5 characters. A string with fewer than 5 characters cannot contain all 5 vowels. Return 0 immediately.
- Missing edge cases with consonants mixed in. "aebcdefgiou" has all vowels starting from index 0 at position 9. Substrings [0:9], [0:10], [0:11] are valid. Consonants between vowels do not break the substring.