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 <= 250word consists only of lowercase English letters.0 <= k <= word.length - 5Problem Overview: Given a string word and an integer k, count how many substrings contain every vowel (a, e, i, o, u) at least once and exactly k consonants. You need to scan all possible substrings but avoid the naive O(n²) enumeration when possible.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Start every substring at index i and extend it one character at a time to index j. Maintain a small frequency map for vowels and a counter for consonants while expanding the substring. Each step checks whether all five vowels appear at least once and whether the consonant count equals k. Since there are O(n²) substrings and each extension performs constant-time updates, the total time complexity is O(n²) with O(1) auxiliary space (only five vowel counters and a consonant counter). This approach is straightforward and useful for verifying correctness or handling small inputs, but it becomes slow for large strings.
Approach 2: Sliding Window with Vowel Tracking (O(n) time, O(1) space)
The optimal strategy uses a sliding window with two pointers. Expand the right pointer while maintaining a vowel frequency map using a small hash table and a counter for consonants. The key observation: once a window contains all five vowels and satisfies the consonant constraint, every valid extension contributes additional substrings. To handle the "exactly k consonants" requirement efficiently, compute substrings with atMost(k) consonants and subtract those with atMost(k-1). While moving the window, update vowel frequencies and shrink from the left whenever the consonant limit is exceeded. Each character enters and leaves the window at most once, giving O(n) time complexity and constant extra space.
This method relies on fast membership checks for vowels and maintaining counts for characters in the current window. Because the alphabet is small, the memory footprint stays constant. Combining the sliding window with vowel coverage tracking avoids scanning the same substring multiple times.
Recommended for interviews: The brute force solution demonstrates that you understand the substring constraints and how to track vowel presence. Interviewers typically expect the optimized sliding window approach with a small string frequency structure. It reduces the complexity from O(n²) to O(n), which shows strong pattern recognition for substring counting problems.
This approach involves the use of a sliding window to efficiently traverse the string and count valid substrings. We maintain two pointers defining the window and use data structures to track vowels and consonant counts within the window.
This code defines a function countSubstrings which calculates the number of substrings containing every vowel and exactly k consonants using a sliding window approach. The function tracks the number of vowels and consonants within the current window using arrays and counters. Upon matching the criteria (all vowels present, exactly k consonants), it increments the result count.
Time Complexity: O(n), where n is the length of the word. The algorithm effectively slides through the string once using two pointers.
Space Complexity: O(1), since we use constant additional space for the arrays and counters regardless of the input size.
The brute force approach involves checking each substring of the input string and verifying if it contains all vowels and exactly k consonants. This method is less efficient and serves as a baseline.
This brute force implementation assesses every substring and checks if it contains all vowels and exactly k consonants. While straightforward, it iteratively computes presence for each new substring, making it computationally expensive.
Time Complexity: O(n^3), where n is the length of the word, as it checks all possible substrings on possibly full scans for vowels and consonants.
Space Complexity: O(1), employing constant space but with inefficient time overhead.
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 word. The algorithm effectively slides through the string once using two pointers. |
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the word, as it checks all possible substrings on possibly full scans for vowels and consonants. |
| Problem Transformation + Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n²) | O(1) | Good for understanding the constraints and verifying logic on small inputs. |
| Sliding Window with Vowel Frequency | O(n) | O(1) | Best for large strings. Uses two pointers and frequency tracking to count valid substrings efficiently. |
Count of Substrings Containing Every Vowel and K Consonants I || LeetCode Weekly Contest 417 • codi • 1,862 views views
Watch 6 more video solutions →Practice Count of Substrings Containing Every Vowel and K Consonants I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor