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 - 5In 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.
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.
Java
Time Complexity: O(n), handling each character only once.
Space Complexity: O(1), maintaining a few counters and a map for 5 vowels.
| 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. |
Count of Substrings Containing Every Vowel and K Consonants II - Leetcode 3306 - Python • NeetCodeIO • 14,848 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 FleetCodePractice this problem
Open in Editor