Skip to main content
Talentd

Count of Substrings Containing Every Vowel and K Consonants II - Solution & Explanation

MediumHash TableStringSliding Window18 min readAsked at: Amazon, Microsoft, Bloomberg
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given a string word and an integer k, count the number of substrings that contain all five vowels (a, e, i, o, u) at least once and exactly k consonants. The main challenge is scanning all possible substrings efficiently while tracking vowel coverage and consonant counts.

Approach 1: Sliding Window with Frequency Map (O(n) time, O(1) space)

This approach uses a classic sliding window over the string. Maintain two pointers left and right and expand the window while tracking vowel frequencies in a small hash table. A counter tracks how many consonants exist in the current window. When the window contains all five vowels and the consonant count reaches k, the window becomes valid. To avoid checking every substring explicitly, count how many valid starting points exist while shrinking the window from the left. Many implementations compute atMost(k) and subtract atMost(k-1) to derive the number of substrings with exactly k consonants. Each character enters and leaves the window at most once, giving O(n) time and O(1) space because the vowel set size is fixed.

Approach 2: Two Pointers with Vowel Set Tracking (O(n) time, O(1) space)

This variant also uses two pointers but focuses explicitly on tracking the presence of all vowels while managing consonant counts. Maintain a set or frequency array representing the five vowels and update it as the right pointer expands the window. When the window includes all vowels and the consonant count exceeds k, advance the left pointer until the constraint is satisfied again. Every time the window contains all vowels and exactly k consonants, additional substrings can be counted by extending the right boundary while the conditions hold. The algorithm processes the string once, performing constant‑time updates per character, resulting in O(n) time and O(1) space. This technique relies heavily on careful pointer movement and efficient vowel membership checks in a string.

Recommended for interviews: The sliding window formulation is what interviewers usually expect. It demonstrates that you recognize substring counting patterns and know how to transform an "exactly k" constraint into an atMost window calculation. Mentioning a brute force idea (O(n^2) substring enumeration) shows baseline reasoning, but implementing the O(n) sliding window proves you understand how to optimize substring problems.

Approach 1: Sliding Window Approach

In this approach, we use a sliding window to maintain a segment of the string we're exploring. We track the counts of vowels within the current window using a hash map and count the number of consonants separately. The window is expanded by adjusting the start and end indices, ensuring we cover all potential substrings efficiently.

This Python implementation utilizes a sliding window technique and hash maps to track vowels. The window is modified by adjusting the left and right pointers whenever the conditions - all vowels present and k consonants - are satisfied.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string, as each character is processed once.
Space Complexity: O(1), since we only store counts for the vowels and a tally for consonants.

Try this approach in the editor →

Approach 2: Two Pointers with Vowel Set Tracking

This approach involves two pointers: one to incrementally build potential substrings (right) and another to check valid substrings (left). We maintain a set to track found vowels and two counters to monitor the number of vowels and consonants. We adjust the left pointer whenever the substring fails to meet the criteria.

This C++ solution uses two pointers to efficiently find qualifying substrings without re-checking each character unnecessarily. Consonants are incremented/decremented to maintain window validity, and vowels are counted using a hash map.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n), handling each character only once.
Space Complexity: O(1), maintaining a few counters and a map for 5 vowels.

Try this approach in the editor →

Approach 3: Problem Transformation + Sliding Window

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

  1. Find the total number of substrings where each vowel appears at least once and contains at least k consonants, denoted as f(k);
  2. Find the total number of substrings where each vowel appears at least once and contains at least k + 1 consonants, denoted as f(k + 1).

Then the answer is f(k) - f(k + 1).

Therefore, we design a function f(k) to count the total number of substrings where each vowel appears at least once and contains at least k consonants.

We can use a hash table cnt to count the occurrences of each vowel, a variable ans to store the answer, a variable l to record the left boundary of the sliding window, and a variable x to record the number of consonants in the current window.

Traverse the string. If the current character is a vowel, add it to the hash table cnt; otherwise, increment x by one. If x \ge k and the size of the hash table cnt is 5, it means the current window meets the conditions. We then move the left boundary in a loop until the window no longer meets the conditions. At this point, all substrings ending at the right boundary r and with the left boundary in the range [0, .. l - 1] meet the conditions, totaling l substrings. We add l to the answer. Continue traversing the string until the end, and we get f(k).

Finally, we return f(k) - f(k + 1).

The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n), where n is the length of the string, as each character is processed once.
Space Complexity: O(1), since we only store counts for the vowels and a tally for consonants.

Two Pointers with Vowel Set Tracking

Time Complexity: O(n), handling each character only once.
Space Complexity: O(1), maintaining a few counters and a map for 5 vowels.

Problem Transformation + Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Frequency MapO(n)O(1)General optimal solution for substring counting with vowel and consonant constraints
Two Pointers with Vowel Set TrackingO(n)O(1)When implementing direct pointer expansion/shrinking logic without the atMost trick

Video Solution

Count of Substrings Containing Every Vowel and K Consonants II | Leetcode 3306 | codestorywithMIK • codestorywithMIK • 17,058 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count of Substrings Containing Every Vowel and K Consonants II easy or hard?
The problem is generally classified as Medium because it combines multiple constraints: tracking all vowels and enforcing exactly k consonants. Recognizing the sliding window pattern and the atMost(k) trick is the key insight needed to reach the optimal O(n) solution.
Count of Substrings Containing Every Vowel and K Consonants II Python/Java solution
Python and Java implementations usually rely on the sliding window technique with a dictionary or array to store vowel counts. The window expands with the right pointer and shrinks with the left pointer when constraints break. Both implementations achieve O(n) time and O(1) auxiliary space.
How to solve Count of Substrings Containing Every Vowel and K Consonants II in O(n)?
Use a sliding window with two pointers. Track vowel frequencies and maintain a count of consonants inside the window. Compute the number of substrings with at most k consonants and subtract those with at most k-1 to get exactly k. Each pointer moves only forward, producing an O(n) solution.
What is the best approach for Count of Substrings Containing Every Vowel and K Consonants II?
The most efficient approach uses a sliding window with vowel frequency tracking and a consonant counter. The idea is to compute substrings with at most k consonants and subtract those with at most k-1. This converts the "exactly k" requirement into a linear scan. The overall time complexity is O(n) with O(1) extra space.
Is Count of Substrings Containing Every Vowel and K Consonants II asked at Google/Amazon/Meta?
Substring counting problems using sliding window patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve vowel tracking, frequency maps, or exactly-k constraints are common because they test two-pointer optimization and string processing skills.
What data structure is used in Count of Substrings Containing Every Vowel and K Consonants II?
The solution typically uses a hash table or fixed array to track frequencies of the five vowels. Two pointers maintain the sliding window boundaries, and a simple counter tracks consonants. These structures allow constant-time updates while scanning the string.
What is the time complexity of Count of Substrings Containing Every Vowel and K Consonants II?
The optimal solution runs in O(n) time because each character is processed at most twice while expanding and shrinking the sliding window. Vowel tracking uses a fixed-size map or array for the five vowels, so operations are constant time. Space complexity is O(1).

Ready to solve this problem?

Practice Count of Substrings Containing Every Vowel and K Consonants II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Vowel Substrings of a String

Next

Longest Substring Of All Vowels in Order