⚡Flashcard Drill➔
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

  1. Counting substrings with exactly k consonants is again an "at least k minus at least k+1" decomposition.
  2. Define atLeast(x): the number of substrings containing all five vowels and at least x consonants.
  3. atLeast(x) is a sliding window: shrink while the window still contains all five vowels and has at least x consonants, and add the left pointer to the answer (every earlier start is also valid).
  4. 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 is atLeast(k) - atLeast(k+1), since we want exactly k.
  • 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 the else branch handles.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems