Count of Substrings Containing Every Vowel and K Consonants I

Problem Description

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.

Key Insights

• A substring must contain all five vowels at least once.
• The substring must contain exactly k consonants.
• The problem can be solved using a sliding window technique to efficiently track the number of vowels and consonants in the current substring.
• Utilizing a hash table can help maintain counts of characters and validate the conditions for vowels and consonants.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string word. We traverse the string with two pointers. Space Complexity: O(1), since we only need a fixed amount of space for counts (vowels and consonants).

Solution

To solve the problem, we can use the sliding window technique along with a hash table to keep track of the counts of vowels and consonants. We will maintain two pointers to represent the current substring and expand or contract the window based on the counts of vowels and consonants.

1. Initialize two pointers, left and right, to represent the current substring.
2. As you expand right, update the counts of vowels and consonants.
3. Whenever the substring meets the condition of containing all vowels and exactly k consonants, count the valid substrings.
4. Move the left pointer to find other valid substrings while maintaining the conditions.

Code Solutions