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 * 105word consists only of lowercase English letters.0 <= k <= word.length - 5Problem 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.
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.
Python
JavaScript
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.
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.
Time Complexity: O(n), handling each character only once.
Space Complexity: O(1), maintaining a few counters and a map for 5 vowels.
We can transform the problem into solving the following two subproblems:
k consonants, denoted as f(k);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).
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the string, as each character is processed once. |
| Two Pointers with Vowel Set Tracking | Time Complexity: O(n), handling each character only once. |
| Problem Transformation + Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Frequency Map | O(n) | O(1) | General optimal solution for substring counting with vowel and consonant constraints |
| Two Pointers with Vowel Set Tracking | O(n) | O(1) | When implementing direct pointer expansion/shrinking logic without the atMost trick |
Count of Substrings Containing Every Vowel and K Consonants II - Leetcode 3306 - Python • NeetCodeIO • 16,523 views views
Watch 9 more video solutions →Practice Count of Substrings Containing Every Vowel and K Consonants II with our built-in code editor and test cases.
Practice on FleetCode