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. Any character that is not a vowel is considered a consonant.

For example, if word = "aeioubcd" and k = 2, one valid substring would be "aeioubcd" because it contains all five vowels at least once and has exactly 2 consonants ('b' and 'c').

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

Intuition

The key insight is 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 the count of substrings that have all vowels and at least k+1 consonants, we get exactly what we want - substrings with all vowels and exactly k consonants.

This is because:

• Substrings with at least k consonants = Substrings with exactly k consonants + Substrings with exactly k+1 consonants + Substrings with exactly k+2 consonants + ...
• Substrings with at least k+1 consonants = Substrings with exactly k+1 consonants + Substrings with exactly k+2 consonants + ...

Therefore: f(k) - f(k+1) gives us substrings with exactly k consonants.

For the sliding window part, we maintain a window that always satisfies our conditions (all vowels present and at least k consonants). As we expand the window to the right, whenever we have a valid window, we need to count how many valid substrings end at the current position. This count equals the number of possible starting positions, which is the current left boundary position l. This is because any substring starting from positions 0 to l-1 and ending at the current position will contain our valid window and thus be valid.

Learn more about Sliding Window patterns.

Solution Approach

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

Implementation of f(k) using Sliding Window:

1. Data Structures:

   • cnt: A Counter (hash table) to track occurrences 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

2. Expanding the Window (right pointer):

   • Iterate through each character c in word
   • If c is a vowel, add it to cnt
   • If c is a consonant, increment x

3. Contracting the Window (left pointer):

   • When we have a valid window (x >= k and len(cnt) == 5), we need to find the leftmost position where the window remains valid
   • Move the left pointer l to the right while the window is valid:
     • If word[l] is a vowel, decrement its count in cnt
       • If count becomes 0, remove it from cnt
     • If word[l] is a consonant, decrement x
     • Increment l
   • The loop stops when either x < k or we don't have all 5 vowels

4. Counting Valid Substrings:

   • After adjusting the left boundary, all substrings ending at the current position and starting from any position in [0, l-1] are valid
   • Add l to ans (there are exactly l such valid substrings)

5. Final Answer:

   • Return f(k) - f(k + 1) to get substrings with exactly k consonants

Why This Works:

• The sliding window maintains the smallest valid window ending at each position
• By keeping track of when we have all vowels (len(cnt) == 5) and enough consonants (x >= k), we ensure our counting condition
• The subtraction f(k) - f(k + 1) transforms the "at least" problem into an "exactly" problem

Example Walkthrough

Let's walk through a small example with word = "aeioubc" 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) (at least 1 consonant):

Starting with left pointer l = 0, we expand our window:

• i = 0, c = 'a': vowel, add to cnt = {'a': 1}, x = 0 consonants

  • Not valid (need x ≥ 1 and all vowels)

• i = 1, c = 'e': vowel, cnt = {'a': 1, 'e': 1}, x = 0

  • Not valid

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

  • Not valid

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

  • Not valid

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

  • Have all vowels but x < 1, not valid

• i = 5, c = 'b': consonant, x = 1

  • Now valid! (all 5 vowels and x ≥ 1)
  • Contract window: Currently l = 0, window is "aeiouб"
  • Try removing word[0] = 'a': Would lose a vowel, making len(cnt) = 4 < 5
  • Stop contracting, l stays at 0
  • Add l = 0 to answer (0 valid substrings ending at position 5)

• i = 6, c = 'c': consonant, x = 2

  • Valid! (all 5 vowels and x ≥ 1)
  • Contract window: Currently l = 0, window is "aeioubc"
  • Try removing word[0] = 'a': Would lose a vowel
  • Stop contracting, l stays at 0
  • Add l = 0 to answer

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

Computing f(2) (at least 2 consonants):

Reset and expand again:

• i = 0-4: Same as before, accumulating vowels, x = 0
• i = 5, c = 'b': x = 1, not valid (need x ≥ 2)
• i = 6, c = 'c': x = 2
  • Now valid! (all 5 vowels and x ≥ 2)
  • Contract window: Currently l = 0
  • Try removing word[0] = 'a': Would lose a vowel
  • Stop contracting, l stays at 0
  • Add l = 0 to answer

Total for f(2) = 0

Final Answer: f(1) - f(2) = 0 - 0 = 0

This makes sense! The only substring with all vowels and exactly 1 consonant would be something like "aeiouб", but that's not a valid substring since we'd need to skip the 'c'. The full string "aeioubc" has 2 consonants, not 1.

Let's verify with a different example where we expect a non-zero result. Consider word = "aaeioubc" and k = 2:

For f(2), when we reach the end (i = 7, after 'c'), we have all vowels and exactly 2 consonants. The window can start from position 0 or 1 (both 'a's can be removed while keeping all vowels), so l would be 2 after contraction, giving us 2 valid substrings: "aaeioubc" and "aeioubc".

For f(3), we never get 3 consonants, so f(3) = 0.

Result: f(2) - f(3) = 2 - 0 = 2, which correctly counts substrings with exactly 2 consonants.

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. Although there's a nested while loop, each character is added to the window once (when the right pointer moves) and removed from the window at most once (when the left pointer moves), resulting in amortized O(1) operations per character. Therefore, each call to f(k) takes O(n) time, and calling it twice still results in O(2n) = O(n) overall time complexity.

The space complexity is O(1). The algorithm uses a Counter object cnt to track 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. Additionally, the algorithm uses a few integer variables (ans, l, x) which require constant space. Therefore, the total space complexity is O(1).

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

Common Pitfalls

1. Incorrect Window Shrinking Logic

Pitfall: A common mistake is shrinking the window too aggressively or not maintaining the correct invariant. Developers often write:

# INCORRECT: Shrinks window when we have a valid substring
while consonant_count >= min_consonants and len(vowel_counter) == 5:
    # shrink window...

This appears correct but can lead to undercounting. The issue is that after shrinking, we immediately count left_pointer substrings, but some of these substrings might not actually contain all vowels or enough consonants.

Solution: The current implementation is actually correct! The key insight is that we shrink the window while maintaining validity, and stop as soon as the window becomes invalid. At that point, all substrings from indices [0, left_pointer-1] to the current right pointer are valid, which is exactly left_pointer substrings.

2. Off-by-One Error in Counting

Pitfall: Confusing whether to add left_pointer or left_pointer + 1 to the answer:

# INCORRECT: Adding left_pointer + 1
total_substrings += left_pointer + 1

Solution: The correct count is left_pointer because:

• After shrinking, left_pointer points to the first position where the window is NO LONGER valid
• Valid starting positions are from index 0 to left_pointer - 1 (inclusive)
• This gives us exactly left_pointer valid substrings

3. Forgetting to Handle Empty Counter

Pitfall: Not properly removing vowels from the counter when their count reaches zero:

# INCORRECT: Just decrementing without removing
if left_char in "aeiou":
    vowel_counter[left_char] -= 1
    # Missing: removal when count becomes 0

This causes len(vowel_counter) to incorrectly report 5 even when some vowels have zero count.

Solution: Always remove the vowel from the counter when its count reaches zero:

if left_char in "aeiou":
    vowel_counter[left_char] -= 1
    if vowel_counter[left_char] == 0:
        vowel_counter.pop(left_char)  # Critical step!

4. Edge Case: k Larger Than Total Consonants

Pitfall: Not handling cases where k is larger than the total number of consonants in the string:

# May cause issues if not handled properly
word = "aeiou"  # No consonants
k = 1
# Should return 0, but implementation might break

Solution: The current implementation naturally handles this because:

• If k is larger than available consonants, consonant_count >= k will never be true
• The function will return 0, which is correct
• No special edge case handling needed due to the algorithm's design

5. Integer Overflow in Other Languages

Pitfall: In languages like C++ or Java, counting substrings of a long string might cause integer overflow:

// C++ example that might overflow
int total_substrings = 0;
// For a string of length n, maximum substrings is n*(n+1)/2

Solution: Use appropriate data types:

• In C++: use long long instead of int
• In Java: use long instead of int
• Python handles arbitrary precision integers automatically, so this isn't an issue