Problem Description

You are given a string word and a non-negative integer k.

Your task is to count the total number of substrings that satisfy both of the following conditions:

1. The substring contains every vowel ('a', 'e', 'i', 'o', and 'u') at least once
2. The substring contains exactly k consonants

A substring is a contiguous sequence of characters within the string. For this problem, any character that is not a vowel is considered a consonant.

For example, if word = "aeioubcd" and k = 2, one valid substring would be "aeioub" because it contains all five vowels and exactly 2 consonants ('b' and the implied count from the position).

The function should return the total count of all such valid substrings in the given string.

Intuition

The key insight is recognizing that finding substrings with exactly k consonants is tricky to do directly. However, finding substrings with at least k consonants is much easier using a sliding window approach.

Think about it this way: if we can count all substrings that have all vowels and at least k consonants, and then subtract all substrings that have all vowels and at least k+1 consonants, we're left with exactly those substrings that have all vowels and exactly k consonants.

This transforms our problem into: f(k) - f(k+1), where f(k) counts substrings with all vowels and at least k consonants.

Why is f(k) easier to compute? With a sliding window, we can maintain a valid window (one that has all vowels and at least k consonants) and for each valid position of the right pointer, count how many valid substrings end at that position.

The trick is: when our window [l, r] is valid (has all 5 vowels and at least k consonants), we shrink from the left until it becomes invalid. At this point, any substring ending at r and starting anywhere from index 0 to l-1 would be valid. That gives us l valid substrings for this particular right endpoint.

This counting method works because if [l, r] is the minimal valid window ending at r, then adding any characters to the left (indices 0 to l-1) will still maintain validity - we'll still have all vowels and at least k consonants.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements the transformation f(k) - f(k+1) using a helper function f(k) that counts substrings with all vowels and at least k consonants.

Implementation of f(k):

1. Data Structures:

   • cnt: A Counter (hash table) to track the frequency of each vowel in the current window
   • x: Counter for the number of consonants in the current window
   • l: Left pointer of the sliding window
   • ans: Accumulator for the total count of valid substrings

2. Sliding Window Algorithm:

   For each character c at position r (right pointer):

   • If c is a vowel, increment its count in cnt
   • If c is a consonant, increment x

3. Shrinking the Window:

   When the window becomes valid (x >= k and len(cnt) == 5):

   • Shrink from the left while maintaining validity
   • For each left character d = word[l]:
     • If d is a vowel: decrement its count and remove from cnt if count becomes 0
     • If d is a consonant: decrement x
     • Increment l
   • Stop shrinking when the window becomes invalid

4. Counting Valid Substrings:

   After shrinking, l represents the leftmost position where the window [l, r] would be invalid. This means:

   • All substrings ending at r and starting at positions [0, 1, ..., l-1] are valid
   • There are exactly l such substrings
   • Add l to ans

5. Final Answer:

   Return f(k) - f(k+1) to get the count of substrings with exactly k consonants.

Why This Works:

The algorithm efficiently counts all substrings with at least k consonants by recognizing that once we have a minimal valid window ending at position r, any extension to the left maintains validity. By computing f(k) - f(k+1), we isolate substrings with exactly k consonants, since substrings with k+1 or more consonants are counted in both f(k) and f(k+1), and their difference cancels them out.

Example Walkthrough

Let's walk through a small example with word = "aeioubcd" and k = 1.

We need to find substrings with all 5 vowels and exactly 1 consonant. Using our approach, we'll calculate f(1) - f(2).

Computing f(1) - substrings with all vowels and at least 1 consonant:

Starting with l = 0, we'll expand our right pointer r:

• r = 0: 'a' (vowel), cnt = {'a': 1}, x = 0 consonants

  • Not valid (need all 5 vowels and at least 1 consonant)
  • No substrings counted

• r = 1: 'e' (vowel), cnt = {'a': 1, 'e': 1}, x = 0

  • Not valid
  • No substrings counted

• r = 2: 'i' (vowel), cnt = {'a': 1, 'e': 1, 'i': 1}, x = 0

  • Not valid
  • No substrings counted

• r = 3: 'o' (vowel), cnt = {'a': 1, 'e': 1, 'i': 1, 'o': 1}, x = 0

  • Not valid
  • No substrings counted

• r = 4: 'u' (vowel), cnt = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}, x = 0

  • Not valid (have all vowels but no consonants)
  • No substrings counted

• r = 5: 'b' (consonant), cnt = all 5 vowels, x = 1`

  • Valid! (all vowels and 1 consonant)
  • Shrink from left while maintaining validity:
    • Window [0,5] "aeioub" is valid
    • Try removing 'a': would still have 1 consonant but lose a vowel → invalid
    • Stop shrinking at l = 0
  • Count: l = 0, so 0 valid substrings ending at position 5

• r = 6: 'c' (consonant), cnt = all 5 vowels, x = 2`

  • Valid! (all vowels and 2 consonants)
  • Shrink from left:
    • Window [0,6] "aeioubc" has 2 consonants
    • Remove 'a': [1,6] "eioubc" still has all vowels and 2 consonants → still valid
    • Remove 'e': [2,6] "ioubc" loses 'e' vowel → becomes invalid
    • Stop at l = 2
  • Count: 2 valid substrings ending at position 6 ([0,6] and [1,6])

• r = 7: 'd' (consonant), cnt = all 5 vowels, x = 3`

  • Valid! (all vowels and 3 consonants)
  • Shrink from left:
    • Keep removing while valid...
    • Stop at l = 3 (removing 'o' would make it invalid)
  • Count: 3 valid substrings ending at position 7

Total for f(1) = 0 + 2 + 3 = 5

Computing f(2) - substrings with all vowels and at least 2 consonants:

Following similar logic:

• Positions 0-5: Not valid (only 0-1 consonants)
• Position 6: 'c' gives us 2 consonants, window becomes valid
  • After shrinking, l = 0
  • Count: 0
• Position 7: 'd' gives us 3 consonants
  • After shrinking, l = 2
  • Count: 2

Total for f(2) = 0 + 2 = 2

Final Answer: f(1) - f(2) = 5 - 2 = 3

The 3 substrings with exactly 1 consonant are:

1. "aeioub" (all vowels + 'b')
2. "eioub" (all vowels + 'b')
3. "ioub" (contains 'i','o','u' from original positions and would need checking for 'a','e')

This demonstrates how the sliding window efficiently counts valid substrings by maintaining the minimal valid window and counting all possible left extensions.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. The function f(k) is called twice - once with parameter k and once with parameter k+1. Each call to f(k) involves a single pass through the string using a sliding window approach. In the sliding window, each character is visited at most twice - once when expanding the window (adding to the right) and once when shrinking the window (removing from the left). Therefore, despite the nested while loop, the amortized time complexity for each call to f(k) is O(n), making the overall time complexity O(n) + O(n) = O(n).

The space complexity is O(1). The algorithm uses a Counter object cnt to store vowel frequencies, but since there are only 5 vowels (a, e, i, o, u), the Counter will store at most 5 key-value pairs regardless of the input size. The variable x tracks consonant count, and variables ans and l are simple integers. All these auxiliary space requirements are constant and independent of the input size n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Window Shrinking Logic

The Pitfall: A common mistake is shrinking the window too aggressively or not understanding when to stop. Developers often write:

# WRONG: Continue shrinking while window is valid
while consonant_count >= min_consonants and len(vowel_counter) == 5 and left_pointer < len(word):
    # shrink window
    left_pointer += 1

This keeps the window valid but doesn't help count all valid substrings correctly.

Why It's Wrong: The algorithm needs to shrink until the window becomes invalid, not maintain validity. When the window [l, r] becomes invalid, it means all substrings from [0, r] to [l-1, r] are valid.

The Fix: Shrink while the window IS valid, and stop when it becomes invalid:

# CORRECT: Shrink while valid, stop when invalid
while consonant_count >= min_consonants and len(vowel_counter) == 5:
    # shrink from left
    # This will naturally stop when window becomes invalid

2. Off-by-One Error in Counting

The Pitfall: After shrinking, developers might incorrectly count valid substrings as left_pointer + 1 or left_pointer - 1.

Why It's Wrong:

• If left_pointer = 3 after shrinking, it means the window [3, r] is invalid
• But windows [0, r], [1, r], [2, r] are all valid
• That's exactly 3 substrings, not 2 or 4

The Fix: Always add exactly left_pointer to the count:

total_substrings += left_pointer  # Correct count

3. Forgetting to Handle Empty Counter

The Pitfall: When decrementing vowel counts, forgetting to remove vowels with zero count:

# WRONG: Just decrement without cleanup
if left_char in "aeiou":
    vowel_counter[left_char] -= 1

Why It's Wrong: This leaves vowels with count 0 in the counter, making len(vowel_counter) always 5 after seeing all vowels once, breaking the validity check.

The Fix: Remove vowels from counter when their count reaches zero:

# CORRECT: Clean up zero counts
if left_char in "aeiou":
    vowel_counter[left_char] -= 1
    if vowel_counter[left_char] == 0:
        vowel_counter.pop(left_char)

4. Misunderstanding the Mathematical Transformation

The Pitfall: Implementing f(k+1) - f(k) instead of f(k) - f(k+1).

Why It's Wrong:

• f(k) counts substrings with ≥k consonants
• f(k+1) counts substrings with ≥k+1 consonants
• f(k) - f(k+1) gives exactly k consonants
• f(k+1) - f(k) would give a negative number!

The Fix: Always use the correct order:

return count_at_least(k) - count_at_least(k + 1)  # Correct