Count of Substrings Containing Every Vowel and K Consonants I Solution
Count of Substrings Containing Every Vowel and K Consonants I solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count of Substrings Containing Every Vowel and K Consonants I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google
- 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
You are given a string word of lowercase English letters and a non-negative integer k.
Return the number of substrings of word that contain every vowel (a, e, i, o and u) at least once and exactly k consonants. Substrings at different positions count separately.
Example 1
Input: word = "uoieax", k = 1
Output: 1
Explanation: Only the whole word has all five vowels and one consonant; `"uoiea"` has all vowels but no consonant.
Example 2
Input: word = "aeiouaeiou", k = 0
Output: 21
Explanation: Every window of length 5 or more holds all five vowels and no consonant: 6 + 5 + 4 + 3 + 2 + 1.
Example 3
Input: word = "aeixou", k = 0
Output: 0
Explanation: Any substring with all five vowels must include the `x`.
Constraints
5 <= word.length <= 250word consists only of lowercase English letters.0 <= k <= word.length - 5
Hints for Count of Substrings Containing Every Vowel and K Consonants I
Hint 1
"Exactly
kconsonants" is awkward for a sliding window, but "at leastmconsonants" is monotone: extending a qualifying substring keeps it qualifying.Hint 2
So count
atLeast(k) - atLeast(k + 1), whereatLeast(m)counts substrings with all five vowels and at leastmconsonants.Hint 3
For
atLeast(m): slideright; while the window has all five vowels and at leastmconsonants, dropword[left]and advanceleft. Then every start beforeleftworks for thisright— addleft.
How to solve Count of Substrings Containing Every Vowel and K Consonants I
Turn the exact count into a difference of two monotone counts. "All vowels and at least m consonants" survives extension, so for each right end the valid starts are a prefix, which a sliding window measures.
Approach
- Define
atLeast(m): keep vowel counts, the number of distinct vowels present, a consonant count,left = 0and a total. - For each
right, addword[right](a vowel's count, or one more consonant). - While the window has all five vowels and at least
mconsonants, removeword[left]and advanceleft. - Add
leftto the total: the starts0 .. left-1all give valid substrings ending atright. - Answer
atLeast(k) - atLeast(k + 1).
Why it works
A substring with exactly k consonants and all vowels is counted by atLeast(k) but not by atLeast(k + 1), and every substring with more consonants is counted by both — so the difference is exactly the requested count. Inside atLeast(m), the shrink loop stops at the first start that fails; every earlier start gives a superset of a valid window and is valid, and since extending to the right keeps validity, left never moves back.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A plain window for "exactly
k" is not monotone: adding a vowel never changes the consonant count, so the valid starts for one end are not a contiguous prefix. - Track distinct vowels:
"aaaaa"has five vowels but only one distinct one. - With
n <= 250an O(n²) scan with early break is also fine; the sliding-window version is what the larger variant (n up to 2·10^5) needs.
Reference solution
Python
def countOfSubstrings(word: str, k: int) -> int:
def at_least(m: int) -> int:
cnt = {}
cons = 0
left = 0
total = 0
for ch in word:
if ch in "aeiou":
cnt[ch] = cnt.get(ch, 0) + 1
else:
cons += 1
while len(cnt) == 5 and cons >= m:
d = word[left]
if d in "aeiou":
cnt[d] -= 1
if cnt[d] == 0:
del cnt[d]
else:
cons -= 1
left += 1
total += left
return total
return at_least(k) - at_least(k + 1)Java
static boolean isVowel3305(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
static int atLeast3305(String word, int m) {
int[] cnt = new int[26];
int distinct = 0, cons = 0, left = 0, total = 0;
for (int right = 0; right < word.length(); right++) {
char c = word.charAt(right);
if (isVowel3305(c)) { if (cnt[c - 'a']++ == 0) distinct++; } else cons++;
while (distinct == 5 && cons >= m) {
char d = word.charAt(left);
if (isVowel3305(d)) { if (--cnt[d - 'a'] == 0) distinct--; } else cons--;
left++;
}
total += left;
}
return total;
}
public static int countOfSubstrings(String word, int k) {
return atLeast3305(word, k) - atLeast3305(word, k + 1);
}C++
bool isVowel3305(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int atLeast3305(const string& word, int m) {
int cnt[26] = {0};
int distinct = 0, cons = 0, left = 0, total = 0;
for (int right = 0; right < (int) word.size(); right++) {
char c = word[right];
if (isVowel3305(c)) { if (cnt[c - 'a']++ == 0) distinct++; } else cons++;
while (distinct == 5 && cons >= m) {
char d = word[left];
if (isVowel3305(d)) { if (--cnt[d - 'a'] == 0) distinct--; } else cons--;
left++;
}
total += left;
}
return total;
}
int countOfSubstrings(string word, int k) {
return atLeast3305(word, k) - atLeast3305(word, k + 1);
}JavaScript
var countOfSubstrings = function(word, k) {
var isVowel = function(c) {
return c === "a" || c === "e" || c === "i" || c === "o" || c === "u";
};
var atLeast = function(m) {
var cnt = { a: 0, e: 0, i: 0, o: 0, u: 0 };
var distinct = 0, cons = 0, left = 0, total = 0;
for (var right = 0; right < word.length; right++) {
var c = word[right];
if (isVowel(c)) { if (cnt[c]++ === 0) distinct++; } else cons++;
while (distinct === 5 && cons >= m) {
var d = word[left];
if (isVowel(d)) { if (--cnt[d] === 0) distinct--; } else cons--;
left++;
}
total += left;
}
return total;
};
return atLeast(k) - atLeast(k + 1);
};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