Problem Statement in English

You’re given a string word and an integer k. You need to count the number of substrings of word that contain all 5 vowels (a, e, i, o, u) and exactly k consonants.

Approach

The problem with going sliding window on this is that as we move the right pointer to the right the number of consonants can increase as we move the left pointer to the right, while the vowels only increase.

So we approach the problem from an angle that both the number of vowels and consonants can increase. We look for atleast k consonants and all 5 vowels, and then we look for at least k + 1 consonants and all 5 vowels. The difference between the two will give us the number of substrings with exactly k consonants. Neat trick.

And we’re done!

Solution in Python


class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        
        # Helper function: Counts substrings with ALL 5 vowels and >= k consonants
        def atLeastK(k: int) -> int:
            vowels_count = {}
            consonants = 0
            left = 0
            res = 0
            
            for right in range(len(word)):
                char = word[right]
                
                # 1. Add the right character to our window
                if char in "aeiou":
                    vowels_count[char] = vowels_count.get(char, 0) + 1
                else:
                    consonants += 1
                
                # 2. While the window is valid, shrink it from the left
                while len(vowels_count) == 5 and consonants >= k:
                    left_char = word[left]
                    if left_char in "aeiou":
                        vowels_count[left_char] -= 1
                        if vowels_count[left_char] == 0:
                            del vowels_count[left_char]
                    else:
                        consonants -= 1
                    
                    left += 1
                
                # 3. Add the number of valid starting positions to our result
                res += left
                
            return res

        # The magic formula
        return atLeastK(k) - atLeastK(k + 1)

Complexity

  • Time: $O(n)$
    Since we traverse the string a few times with the two-pointer technique.

  • Space: $O(1)$
    Since we only store counts of vowels and consonants, which is constant space.

Mistakes I Made

I had to look this one up :(

And we are done.