Count Vowel Substrings of a String
Asked at Salesforce
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | Easy | View all Salesforce 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Vowel Substrings of a String?
Count Vowel Substrings of a String is asked at Salesforce. 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.