NeetCode #253LC-3306MediumSliding Window
← Back to All Problems#253 · #3306 · Count of Substrings Containing Every Vowel and K Consonants II(元音辅音字符串计数 II)
📌 Problem Statement & Constraints
You are given a string
word and a non-negative integer k. Return the number of substrings that contain every vowel (a, e, i, o, u) at least once and exactly k consonants. Constraints: 5 <= word.length <= 2 * 10^5, 0 <= k <= word.length - 5; word consists of lowercase English letters and digits.💡 Core Algorithmic Approaches
- Counting substrings with exactly
kconsonants is again an "at least k minus at least k+1" decomposition. - Define
atLeast(x): the number of substrings containing all five vowels and at leastxconsonants. atLeast(x)is a sliding window: shrink while the window still contains all five vowels and has at leastxconsonants, and add the left pointer to the answer (every earlier start is also valid).- The answer is
atLeast(k) - atLeast(k + 1).
💻 Benchmark Python3 Implementation
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
from collections import defaultdict
vowels = set("aeiou")
def atLeast(x: int) -> int:
if x < 0:
return 0
cnt = defaultdict(int)
cons = 0
l = 0
res = 0
for r, ch in enumerate(word):
if ch in vowels:
cnt[ch] += 1
else:
cons += 1
# shrink while the window still satisfies both conditions
while len(cnt) == 5 and cons >= x:
out = word[l]
if out in vowels:
cnt[out] -= 1
if cnt[out] == 0:
del cnt[out]
else:
cons -= 1
l += 1
res += l # all starts in [0, l-1] are valid
return res
return atLeast(k) - atLeast(k + 1)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two linear passes with monotone pointers.
💾 Space Complexity
O(1): the counter holds at most 5 vowel keys.
⚠️ Interview Pitfalls & Follow-ups
- Trying to count exactly k directly: the window is not uniquely determined, so the subtraction decomposition is needed.
- Using
atLeast(k) - atLeast(k-1): the direction is wrong -- the answer isatLeast(k) - atLeast(k+1), since we want exactlyk. - Forgetting to delete zero-count vowel keys:
len(cnt)would overcount and the shrink would stop too early. - Treating digits as vowels or consonants: the statement allows digits in
word; they are consonants for this purpose, which theelsebranch handles.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner