Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
You are given a string word and a non-negative integer k.
Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.
Example 1:
Input: word = "aeioqq", k = 1
Output: 0
Explanation:
There is no substring with every vowel.
Example 2:
Input: word = "aeiou", k = 0
Output: 1
Explanation:
The only substring with every vowel and zero consonants is word[0..4], which is "aeiou".
Example 3:
Input: word = "ieaouqqieaouqq", k = 1
Output: 3
Explanation:
The substrings with every vowel and one consonant are:
word[0..5], which is "ieaouq".word[6..11], which is "qieaou".word[7..12], which is "ieaouq".Constraints:
5 <= word.length <= 2 * 105word consists only of lowercase English letters.0 <= k <= word.length - 5Problem summary: You are given a string word and a non-negative integer k. Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Sliding Window
"aeioqq" 1
"aeiou" 0
"ieaouqqieaouqq" 1
longest-substring-of-all-vowels-in-order)count-vowel-substrings-of-a-string)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3306: Count of Substrings Containing Every Vowel and K Consonants II
class Solution {
public long countOfSubstrings(String word, int k) {
return f(word, k) - f(word, k + 1);
}
private long f(String word, int k) {
long ans = 0;
int l = 0, x = 0;
Map<Character, Integer> cnt = new HashMap<>(5);
for (char c : word.toCharArray()) {
if (vowel(c)) {
cnt.merge(c, 1, Integer::sum);
} else {
++x;
}
while (x >= k && cnt.size() == 5) {
char d = word.charAt(l++);
if (vowel(d)) {
if (cnt.merge(d, -1, Integer::sum) == 0) {
cnt.remove(d);
}
} else {
--x;
}
}
ans += l;
}
return ans;
}
private boolean vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}
// Accepted solution for LeetCode #3306: Count of Substrings Containing Every Vowel and K Consonants II
func countOfSubstrings(word string, k int) int64 {
f := func(k int) int64 {
var ans int64 = 0
l, x := 0, 0
cnt := make(map[rune]int)
vowel := func(c rune) bool {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
}
for _, c := range word {
if vowel(c) {
cnt[c]++
} else {
x++
}
for x >= k && len(cnt) == 5 {
d := rune(word[l])
l++
if vowel(d) {
cnt[d]--
if cnt[d] == 0 {
delete(cnt, d)
}
} else {
x--
}
}
ans += int64(l)
}
return ans
}
return f(k) - f(k+1)
}
# Accepted solution for LeetCode #3306: Count of Substrings Containing Every Vowel and K Consonants II
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
def f(k: int) -> int:
cnt = Counter()
ans = l = x = 0
for c in word:
if c in "aeiou":
cnt[c] += 1
else:
x += 1
while x >= k and len(cnt) == 5:
d = word[l]
if d in "aeiou":
cnt[d] -= 1
if cnt[d] == 0:
cnt.pop(d)
else:
x -= 1
l += 1
ans += l
return ans
return f(k) - f(k + 1)
// Accepted solution for LeetCode #3306: Count of Substrings Containing Every Vowel and K Consonants II
impl Solution {
pub fn count_of_substrings(word: String, k: i32) -> i64 {
fn f(word: &Vec<char>, k: i32) -> i64 {
let mut ans = 0_i64;
let mut l = 0;
let mut x = 0;
let mut cnt = std::collections::HashMap::new();
let is_vowel = |c: char| matches!(c, 'a' | 'e' | 'i' | 'o' | 'u');
for (r, &c) in word.iter().enumerate() {
if is_vowel(c) {
*cnt.entry(c).or_insert(0) += 1;
} else {
x += 1;
}
while x >= k && cnt.len() == 5 {
let d = word[l];
l += 1;
if is_vowel(d) {
let count = cnt.entry(d).or_insert(0);
*count -= 1;
if *count == 0 {
cnt.remove(&d);
}
} else {
x -= 1;
}
}
ans += l as i64;
}
ans
}
let chars: Vec<char> = word.chars().collect();
f(&chars, k) - f(&chars, k + 1)
}
}
// Accepted solution for LeetCode #3306: Count of Substrings Containing Every Vowel and K Consonants II
function countOfSubstrings(word: string, k: number): number {
const f = (k: number): number => {
let ans = 0;
let l = 0,
x = 0;
const cnt = new Map<string, number>();
const vowel = (c: string): boolean => {
return c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u';
};
for (const c of word) {
if (vowel(c)) {
cnt.set(c, (cnt.get(c) || 0) + 1);
} else {
x++;
}
while (x >= k && cnt.size === 5) {
const d = word[l++];
if (vowel(d)) {
cnt.set(d, cnt.get(d)! - 1);
if (cnt.get(d) === 0) {
cnt.delete(d);
}
} else {
x--;
}
}
ans += l;
}
return ans;
};
return f(k) - f(k + 1);
}
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.