#3305

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count of Substrings Containing Every Vowel and K Consonants I

Count all substrings containing every vowel and exactly k consonants using a sliding window and hash map state tracking.

hash table string sliding window

Problem Statement

Given a lowercase string word and a non-negative integer k, determine the total number of substrings that include every vowel ('a', 'e', 'i', 'o', 'u') at least once and contain exactly k consonants. Substrings must maintain the original order of letters in word.

Return the total count of such substrings. Constraints: word length is between 5 and 250, word contains only lowercase letters, and 0 <= k <= word.length - 5. Examples include word = 'aeioqq' with k = 1 returning 0, and word = 'aeiou' with k = 0 returning 1.

Examples

Example 1

Input: word = "aeioqq", k = 1

Output: 0

There is no substring with every vowel.

Example 2

Input: word = "aeiou", k = 0

Output: 1

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

The substrings with every vowel and one consonant are:

Constraints

5 <= word.length <= 250
word consists only of lowercase English letters.
0 <= k <= word.length - 5

Solution Approach

Sliding Window with Hash Map

Use two pointers to define a window and a hash map to track vowel counts. Expand the window to include new letters and shrink it when consonants exceed k.

Validate Window for All Vowels

For each valid window, check the hash map to ensure all vowels appear at least once. Only windows meeting this condition and exactly k consonants are counted.

Count Valid Substrings Efficiently

Instead of checking all substrings, incrementally update counts while sliding the window. This reduces repeated computations and ensures time complexity stays manageable.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for sliding through the string with constant-time hash map updates per letter. Space complexity is O(1) for the hash map since vowels are limited and consonant counting uses constant space.

What Interviewers Usually Probe

Check that all vowels exist before counting the substring.
Watch for off-by-one errors when managing the window boundaries.
Confirm consonant count matches exactly k while expanding or shrinking.

Common Pitfalls or Variants

Common pitfalls

Forgetting to remove consonants when shrinking the window.
Counting windows that include all vowels but exceed k consonants.
Using nested loops for substring generation instead of sliding window.

Follow-up variants

Count substrings containing all vowels and at most k consonants.
Count substrings containing all vowels and a range of consonants from k to m.
Count substrings containing all vowels and exactly k specific consonants only.

FAQ

What is the main pattern used in Count of Substrings Containing Every Vowel and K Consonants I?

The primary pattern is sliding window with running state updates using a hash map to track vowels and consonants.

How do I efficiently check all vowels in a substring?

Use a hash map to count each vowel within the window and verify that all five vowels have a positive count.

Can consonants be counted while expanding the window?

Yes, maintain a running consonant counter and adjust when the window grows or shrinks to keep exactly k consonants.

What happens if the window exceeds k consonants?

Shrink the window from the left until consonant count equals k before counting valid substrings.

Are there edge cases for minimal length substrings?

Yes, ensure the substring is at least length 5 to contain all vowels, and check for zero consonants when k is 0.

terminal

Solution

Solution 1: Problem Transformation + Sliding Window

We can transform the problem into solving the following two subproblems:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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)

Continue Practicing

#3306 count of substrings containing every vowel and k consonants ii #3298 count substrings that can be rearranged to contain a string ii #3297 count substrings that can be rearranged to contain a string i