#3306

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count of Substrings Containing Every Vowel and K Consonants II

Count the number of substrings containing all vowels and exactly k consonants using a sliding window technique.

Problem Statement

Given a string word and an integer k, your task is to return the total number of substrings in word that contain every vowel ('a', 'e', 'i', 'o', 'u') at least once and exactly k consonants.

The length of the word can range from 5 to 2 * 10^5 characters, and you are required to find a solution using a sliding window approach that tracks the count of vowels and consonants dynamically.

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 <= 2 * 105
word consists only of lowercase English letters.
0 <= k <= word.length - 5

Solution Approach

Sliding Window with Running State Updates

The sliding window approach allows you to keep track of the number of vowels and consonants in a dynamic window. As you expand or contract the window, update the counts of each vowel and consonant in constant time. The window should only include substrings that have all vowels and exactly k consonants.

Binary Search Optimization

Binary search can be used to further optimize the solution by helping you efficiently find valid windows or calculate substring boundaries within the sliding window.

Hash Map for Tracking Vowels and Consonants

Use a hash map or array to store the count of vowels and consonants within the window. This ensures that you are dynamically updating and checking the condition of having every vowel and exactly k consonants at each step.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N) because the sliding window ensures that each character is processed at most twice (once when entering the window and once when leaving). The space complexity is O(1), as only a fixed number of counters are maintained for vowels and consonants.

What Interviewers Usually Probe

Can the candidate efficiently use sliding window to track both vowels and consonants?
Does the candidate optimize with binary search or other techniques?
Is the candidate able to handle large input sizes within time constraints?

Common Pitfalls or Variants

Common pitfalls

Failing to maintain the count of vowels or consonants accurately inside the sliding window.
Not properly managing the boundary conditions for the sliding window.
Overcomplicating the problem instead of leveraging the sliding window and running state updates effectively.

Follow-up variants

What if k is allowed to vary or if there are additional constraints on the consonants?
How would this problem be affected if the vowels were not fixed to 'a', 'e', 'i', 'o', 'u'?
Could the problem be extended to require substrings with multiple vowel occurrences?

FAQ

What is the key pattern in solving the 'Count of Substrings Containing Every Vowel and K Consonants II' problem?

The main pattern is using the sliding window with running state updates, which tracks the number of vowels and consonants dynamically as the window expands or contracts.

How do I optimize my solution for large input sizes in this problem?

You can optimize your solution by using binary search in conjunction with the sliding window, ensuring efficient calculation of valid substring boundaries.

What if I can't count the vowels or consonants correctly within the sliding window?

A common pitfall is incorrect maintenance of vowel and consonant counts. Make sure to adjust the counts properly when characters enter or leave the window.

Can I use any data structure to keep track of vowels and consonants?

Yes, you can use a hash map or an array to store the counts of vowels and consonants within the window. Both provide constant time updates as the window slides.

How can I deal with the constraint that the string length can be up to 2 * 10^5?

The sliding window approach ensures that you only process each character a few times, making it feasible to solve the problem within the time constraints of large input sizes.

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

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