We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count of Substrings Containing Every Vowel and K Consonants II

Difficulty: Medium

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.
  • A sliding window approach can be used to efficiently explore potential substrings.
  • Hash tables can be utilized to keep track of the counts of vowels and consonants in the current window.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (for the counts of vowels and consonants)

Solution

The solution employs a sliding window technique to traverse through the string while maintaining a count of vowels and consonants in the current window. The algorithm expands the window rightwards until all vowels are included and then contracts the window from the left to maintain exactly k consonants. Whenever the conditions are met, the number of valid substrings is incremented based on the current positions of the window.

Code Solutions

def countSubstrings(word: str, k: int) -> int:
    vowels = set('aeiou')
    n = len(word)
    left = 0
    vowel_count = {v: 0 for v in vowels}
    consonant_count = 0
    result = 0
    
    for right in range(n):
        if word[right] in vowels:
            vowel_count[word[right]] += 1
        else:
            consonant_count += 1
        
        while all(vowel_count[v] > 0 for v in vowels) and consonant_count > k:
            if word[left] in vowels:
                vowel_count[word[left]] -= 1
            else:
                consonant_count -= 1
            left += 1
        
        if all(vowel_count[v] > 0 for v in vowels) and consonant_count == k:
            # Count valid substrings
            temp_left = left
            while temp_left <= right and consonant_count == k:
                if word[temp_left] not in vowels:
                    temp_left += 1
                else:
                    break
            result += temp_left - left + 1
            
    return result
← Back to All Questions