Count of Substrings Containing Every Vowel and K Consonants II - Video Solutions

Problem Overview: Given a string word and an integer k, count the number of substrings that contain all five vowels (a, e, i, o, u) at least once and exactly k consonants. The main challenge is scanning all possible substrings efficiently while tracking vowel coverage and consonant counts.

Approach 1: Sliding Window with Frequency Map (O(n) time, O(1) space)

This approach uses a classic sliding window over the string. Maintain two pointers left and right and expand the window while tracking vowel frequencies in a small hash table. A counter tracks how many consonants exist in the current window. When the window contains all five vowels and the consonant count reaches k, the window becomes valid. To avoid checking every substring explicitly, count how many valid starting points exist while shrinking the window from the left. Many implementations compute atMost(k) and subtract atMost(k-1) to derive the number of substrings with exactly k consonants. Each character enters and leaves the window at most once, giving O(n) time and O(1) space because the vowel set size is fixed.

Approach 2: Two Pointers with Vowel Set Tracking (O(n) time, O(1) space)

This variant also uses two pointers but focuses explicitly on tracking the presence of all vowels while managing consonant counts. Maintain a set or frequency array representing the five vowels and update it as the right pointer expands the window. When the window includes all vowels and the consonant count exceeds k, advance the left pointer until the constraint is satisfied again. Every time the window contains all vowels and exactly k consonants, additional substrings can be counted by extending the right boundary while the conditions hold. The algorithm processes the string once, performing constant‑time updates per character, resulting in O(n) time and O(1) space. This technique relies heavily on careful pointer movement and efficient vowel membership checks in a string.

Recommended for interviews: The sliding window formulation is what interviewers usually expect. It demonstrates that you recognize substring counting patterns and know how to transform an "exactly k" constraint into an atMost window calculation. Mentioning a brute force idea (O(n^2) substring enumeration) shows baseline reasoning, but implementing the O(n) sliding window proves you understand how to optimize substring problems.