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

Problem Overview: Given a string word and an integer k, count how many substrings contain every vowel (a, e, i, o, u) at least once and exactly k consonants. You need to scan all possible substrings but avoid the naive O(n²) enumeration when possible.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Start every substring at index i and extend it one character at a time to index j. Maintain a small frequency map for vowels and a counter for consonants while expanding the substring. Each step checks whether all five vowels appear at least once and whether the consonant count equals k. Since there are O(n²) substrings and each extension performs constant-time updates, the total time complexity is O(n²) with O(1) auxiliary space (only five vowel counters and a consonant counter). This approach is straightforward and useful for verifying correctness or handling small inputs, but it becomes slow for large strings.

Approach 2: Sliding Window with Vowel Tracking (O(n) time, O(1) space)

The optimal strategy uses a sliding window with two pointers. Expand the right pointer while maintaining a vowel frequency map using a small hash table and a counter for consonants. The key observation: once a window contains all five vowels and satisfies the consonant constraint, every valid extension contributes additional substrings. To handle the "exactly k consonants" requirement efficiently, compute substrings with atMost(k) consonants and subtract those with atMost(k-1). While moving the window, update vowel frequencies and shrink from the left whenever the consonant limit is exceeded. Each character enters and leaves the window at most once, giving O(n) time complexity and constant extra space.

This method relies on fast membership checks for vowels and maintaining counts for characters in the current window. Because the alphabet is small, the memory footprint stays constant. Combining the sliding window with vowel coverage tracking avoids scanning the same substring multiple times.

Recommended for interviews: The brute force solution demonstrates that you understand the substring constraints and how to track vowel presence. Interviewers typically expect the optimized sliding window approach with a small string frequency structure. It reduces the complexity from O(n²) to O(n), which shows strong pattern recognition for substring counting problems.