Count Vowel Substrings of a String — Problem & Solution
Count Vowel Substrings of a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Vowel Substrings of a String is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Cognizant interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A vowel substring is a contiguous substring made up only of vowels (a, e, i, o, u) that contains all five of them at least once.
Return the number of vowel substrings of word.
Example 1
Input: word = "aeiouu"
Output: 2
Explanation: `aeiou` and `aeiouu`.
Example 2
Input: word = "codekairo"
Output: 0
Explanation: Consonants break every run, so no all-vowel substring exists.
Example 3
Input: word = "cuaieuouac"
Output: 7
Constraints
1 <= word.length <= 100word consists of lowercase English letters only.
Hints for Count Vowel Substrings of a String
Hint 1
A consonant ends every candidate — the substring must be entirely vowels.
Hint 2
For each starting index, extend right while the characters stay vowels and count once all five have appeared.
Hint 3
At
n <= 100the quadratic enumeration is comfortable.
How to solve Count Vowel Substrings of a String
For each start index, extend a window right while the characters remain vowels, tracking how many distinct vowels have been seen. Every extension after the fifth distinct vowel arrives is another valid substring.
Approach
- For each
i, reset a set of seen vowels. - Extend
jfromi; break out on a consonant. - Count the substring whenever the set holds all five vowels.
Why it works
Breaking on a consonant is what keeps this near-linear in practice — the inner loop never crosses one, so the total work is the sum of the squares of the vowel-run lengths, not n². The sliding-window version tracks the smallest window covering all five and adds its left-extension count, which is O(n) but far harder to get exactly right.
Complexity
- Time —
O(n²) in the worst case, and much less when consonants are common - Space —
O(1) — at most five distinct vowels
Pitfalls
- The substring must contain no consonants, not merely start and end with vowels.
- All five vowels are required — four is not enough.
- Longer substrings that still qualify each count separately.
Reference solution
Python
def countVowelSubstrings(word: str) -> int:
vowels = set("aeiou")
count = 0
for i in range(len(word)):
seen = set()
for j in range(i, len(word)):
if word[j] not in vowels:
break
seen.add(word[j])
if len(seen) == 5:
count += 1
return countJava
public static int countVowelSubstrings(String word) {
String V = "aeiou";
int count = 0;
for (int i = 0; i < word.length(); i++) {
boolean[] seen = new boolean[5];
int distinct = 0;
for (int j = i; j < word.length(); j++) {
int idx = V.indexOf(word.charAt(j));
if (idx < 0) break;
if (!seen[idx]) { seen[idx] = true; distinct++; }
if (distinct == 5) count++;
}
}
return count;
}C++
int countVowelSubstrings(string word) {
string V = "aeiou";
int count = 0;
for (int i = 0; i < (int) word.size(); i++) {
bool seen[5] = {false, false, false, false, false};
int distinct = 0;
for (int j = i; j < (int) word.size(); j++) {
size_t idx = V.find(word[j]);
if (idx == string::npos) break;
if (!seen[idx]) { seen[idx] = true; distinct++; }
if (distinct == 5) count++;
}
}
return count;
}JavaScript
var countVowelSubstrings = function(word) {
var V = "aeiou", count = 0;
for (var i = 0; i < word.length; i++) {
var seen = {}, distinct = 0;
for (var j = i; j < word.length; j++) {
var c = word.charAt(j);
if (V.indexOf(c) === -1) break;
if (!seen[c]) { seen[c] = true; distinct++; }
if (distinct === 5) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets