Count of Substrings Containing Every Vowel and K Consonants II

Problem Statement

Given a string word and a non-negative integer k, return the total number of substrings of word that satisfy both of the following conditions:

• Contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once.
• Contain exactly k consonants.

Explanation

The task is to count all contiguous substrings of the input string word that:

• Include all the vowels: a, e, i, o, and u.
• Have exactly k consonants (letters that are not vowels).

Constraints

• 5 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.
• 0 <= k <= word.length - 5

Examples

Example 1

• Input: word = "cuaeio", k = 1
• Explanation:
  The only valid substring is "cuaeio". It contains all vowels (u, a, e, i, o) and exactly 1 consonant (c).
• Output: 1

Example 2

• Input: word = "aeioubt", k = 2
• Explanation:
  The substring "aeioubt" has all vowels and exactly 2 consonants (b and t). No other substring meets the criteria.
• Output: 1

Example 3

• Input: word = "abaeiou", k = 1
• Explanation:
  There are two valid substrings:
  • "baeiou" (from index 1 to 6) contains vowels (a, e, i, o, u) and 1 consonant (b).
  • "abaeiou" (from index 0 to 6) also contains all vowels and exactly 1 consonant (b).
• Output: 2

Constraints

• $5 <= word.length <= 2 * 10^5$
• word consists only of lowercase English letters.
• $0 <= k <= word.length - 5$