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 <= 250word 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 #3305: Count of Substrings Containing Every Vowel and K Consonants I
class Solution {
public int countOfSubstrings(String word, int k) {
return f(word, k) - f(word, k + 1);
}
private int f(String word, int k) {
int 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 #3305: Count of Substrings Containing Every Vowel and K Consonants I
func countOfSubstrings(word string, k int) int {
f := func(k int) int {
var ans int = 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 += l
}
return ans
}
return f(k) - f(k+1)
}
# Accepted solution for LeetCode #3305: Count of Substrings Containing Every Vowel and K Consonants I
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 #3305: Count of Substrings Containing Every Vowel and K Consonants I
impl Solution {
pub fn count_of_substrings(word: String, k: i32) -> i32 {
fn f(word: &Vec<char>, k: i32) -> i32 {
let mut ans = 0;
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 i32;
}
ans
}
let chars: Vec<char> = word.chars().collect();
f(&chars, k) - f(&chars, k + 1)
}
}
// Accepted solution for LeetCode #3305: Count of Substrings Containing Every Vowel and K Consonants I
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.