# Count of Substrings Containing Every Vowel and K Consonants I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-of-substrings-containing-every-vowel-and-k-consonants-i)
Canonical: https://scaleengineer.com/dsa/problems/count-of-substrings-containing-every-vowel-and-k-consonants-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
---
## Problem
You are given a string `word` and a **non-negative** integer `k`.

Return the total number of substrings of `word` that contain every vowel (`'a'`, `'e'`, `'i'`, `'o'`, and `'u'`) **at least** once and **exactly** `k` consonants.

**Example 1:**

**Input:** word = "aeioqq", k = 1

**Output:** 0

**Explanation:**

There is no substring with every vowel.

**Example 2:**

**Input:** word = "aeiou", k = 0

**Output:** 1

**Explanation:**

The only substring with every vowel and zero consonants is `word[0..4]`, which is `"aeiou"`.

**Example 3:**

**Input:** word = "ieaouqqieaouqq", k = 1

**Output:** 3

**Explanation:**

The substrings with every vowel and one consonant are:

* `word[0..5]`, which is `"ieaouq"`.
* `word[6..11]`, which is `"qieaou"`.
* `word[7..12]`, which is `"ieaouq"`.

**Constraints:**

* `5 <= word.length <= 250`
* `word` consists only of lowercase English letters.
* `0 <= k <= word.length - 5`

# Approaches
## Optimized Brute Force
This approach iterates through all possible substrings of the given `word`. For each starting position, it expands the substring one character at a time to the right, keeping a running count of the number of consonants and the set of unique vowels encountered. This avoids re-calculating these counts for every single substring from scratch.
**Time:** O(N^2), where N is the length of `word`. The two nested loops iterate through approximately N^2/2 substrings, and the work inside the inner loop is O(1). · **Space:** O(1), as the space used for tracking vowels (e.g., a boolean array of size 5 or a set of max size 5) and the consonant count is constant regardless of the input string size.
**Pros:** Simple to conceptualize and implement.; It is a correct, brute-force solution that directly models the problem statement.
**Cons:** The time complexity is quadratic, which might be too slow if the input string length `N` were much larger. For the given constraints (`N <= 250`), it should pass, but it's not the most optimal solution.
### Explanation
The most straightforward way to solve this problem is to check every possible substring. We can use two nested loops to define the start and end points of a substring. The outer loop fixes the starting index `i`, and the inner loop iterates the ending index `j` from `i` to the end of the string.

For each starting index `i`, we initialize a consonant counter and a data structure to keep track of the unique vowels seen so far (a boolean array or a hash set works well). As we extend the substring by moving the end pointer `j`, we update these counts based on the character `word.charAt(j)`. After adding each new character, we check if the current substring `word[i..j]` satisfies the problem's criteria: containing all five vowels and exactly `k` consonants. If it does, we increment our result counter.

This method is easy to understand because it directly translates the problem statement into code, but its performance is not optimal due to the nested loops.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int countSubstrings(String word, int k) {
        int n = word.length();
        int result = 0;

        for (int i = 0; i < n; i++) {
            int consonants = 0;
            // Using a boolean array for vowels 'a','e','i','o','u'
            boolean[] vowelsFound = new boolean[5];
            int distinctVowels = 0;

            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (isVowel(c)) {
                    int vowelIndex = "aeiou".indexOf(c);
                    if (!vowelsFound[vowelIndex]) {
                        vowelsFound[vowelIndex] = true;
                        distinctVowels++;
                    }
                } else {
                    consonants++;
                }

                if (distinctVowels == 5 && consonants == k) {
                    result++;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a helper function `isVowel(char c)` that returns true if `c` is a vowel.
- Initialize a result counter `count` to 0.
- Iterate through the string with an outer loop using index `i` from 0 to `word.length() - 1`. This `i` will be the starting index of our substrings.
- For each `i`, start an inner loop with index `j` from `i` to `word.length() - 1`. This `j` will be the ending index.
- Inside the inner loop, for each substring `word[i..j]`, maintain a count of consonants and a way to track unique vowels (e.g., a set or a frequency map).
- As `j` increments, update the consonant and vowel counts for the current character `word.charAt(j)`.
- After each update, check if the two conditions are met for the substring `word[i..j]`:
  1. The number of unique vowels is 5.
  2. The number of consonants is exactly `k`.
- If both conditions are true, increment the `count`.
- After the loops complete, return the total `count`.

## Sliding Window with Inclusion-Exclusion
A more efficient approach uses the sliding window technique combined with the inclusion-exclusion principle. The condition of having *exactly* `k` consonants is difficult to handle directly in a standard sliding window because the property is not monotonic. However, the property of having *at most* `k` consonants is monotonic and can be handled efficiently.

We can find the number of substrings with all vowels and exactly `k` consonants by calculating the number of substrings with all vowels and *at most* `k` consonants, and then subtracting the number of substrings with all vowels and *at most* `k-1` consonants.
**Time:** O(N), where N is the length of `word`. The `countAtMost` function is called twice, and inside it, each of the three pointers (`right`, `left_consonant`, `left_vowel`) traverses the string at most once. · **Space:** O(1), since the `vowelCounts` array has a fixed size (26), and other variables use constant space.
**Pros:** Extremely efficient with a linear time complexity.; Scales well to much larger input sizes beyond the given constraints.
**Cons:** The logic is significantly more complex than the brute-force approach.; The inclusion-exclusion principle (`at most k` - `at most k-1`) might not be immediately obvious.
### Explanation
This linear-time solution is built upon a helper function that solves a slightly different problem: counting substrings with all vowels and *at most* a given number of consonants, say `C`. Let's call this function `countAtMost(C)`. The original problem for *exactly* `k` consonants can then be solved by computing `countAtMost(k) - countAtMost(k-1)`.

The `countAtMost(C)` function is implemented using an advanced sliding window technique with three pointers: `right`, `left_consonant`, and `left_vowel`. 

1.  The `right` pointer iterates through the string from left to right, expanding the window.
2.  The `left_consonant` pointer maintains the left boundary of a window `[left_consonant..right]` that has at most `C` consonants. If adding `word[right]` makes the consonant count exceed `C`, `left_consonant` is moved to the right until the condition is met again.
3.  The `left_vowel` pointer maintains the left boundary of a window that contains all five vowels. It is moved to the right as long as the window `[left_vowel..right]` still has all five vowels. After its loop, `word[left_vowel-1..right]` is the shortest substring ending at `right` with all five vowels.

For each position of `right`, any substring `word[i..right]` is valid if its start `i` satisfies both conditions. This means `i` must be greater than or equal to `left_consonant` and less than or equal to `left_vowel - 1`. The number of such valid starting positions is `max(0, left_vowel - left_consonant)`. Summing this up for all `right` gives the result for `countAtMost(C)`.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int countSubstrings(String word, int k) {
        return countAtMost(word, k) - countAtMost(word, k - 1);
    }

    private int countAtMost(String word, int maxConsonants) {
        if (maxConsonants < 0) {
            return 0;
        }
        int n = word.length();
        int count = 0;
        int leftConsonant = 0;
        int leftVowel = 0;
        int consonantCount = 0;
        int[] vowelCounts = new int[26];
        int distinctVowelCount = 0;

        for (int right = 0; right < n; right++) {
            char charRight = word.charAt(right);
            if (isVowel(charRight)) {
                if (vowelCounts[charRight - 'a'] == 0) {
                    distinctVowelCount++;
                }
                vowelCounts[charRight - 'a']++;
            } else {
                consonantCount++;
            }

            while (consonantCount > maxConsonants) {
                char charLeftC = word.charAt(leftConsonant);
                if (!isVowel(charLeftC)) {
                    consonantCount--;
                }
                leftConsonant++;
            }

            while (distinctVowelCount == 5) {
                char charLeftV = word.charAt(leftVowel);
                if (isVowel(charLeftV)) {
                    vowelCounts[charLeftV - 'a']--;
                    if (vowelCounts[charLeftV - 'a'] == 0) {
                        distinctVowelCount--;
                    }
                }
                leftVowel++;
            }
            
            count += (leftVowel - leftConsonant);
        }
        return count;
    }
}
```
### Algorithm
- The main idea is to transform the problem: `count(exactly k) = count(at most k) - count(at most k-1)`.
- We implement a helper function, `countAtMost(max_consonants)`, which counts substrings with all five vowels and at most `max_consonants`.
- The final answer is `countAtMost(k) - countAtMost(k-1)`.
- `countAtMost` uses a sliding window with three pointers: `right`, `left_consonant`, and `left_vowel`.
- The `right` pointer expands the window from left to right through the string.
- For each `right` position, we find the number of valid starting indices `i` for substrings ending at `right`.
- `left_consonant` is advanced to shrink the window from the left, ensuring the substring `word[left_consonant..right]` has at most `max_consonants`.
- `left_vowel` is advanced to find the minimal valid window. It marks the first position `i` such that `word[i..right]` does *not* contain all five vowels. Therefore, any substring starting at an index less than `left_vowel` (and ending at `right`) will have all five vowels.
- For a fixed `right`, any starting index `i` in the range `[left_consonant, left_vowel - 1]` forms a valid substring.
- The number of such substrings is `max(0, left_vowel - left_consonant)`. This value is added to the total count for each step of the `right` pointer.

# Solutions
### Java

```java
class Solution {
public
  int countOfSubstrings(String word, int k) {
    return f(word, k) - f(word, k + 1);
  }
private
  int f(String word, int k) {
    int ans = 0;
    int l = 0, x = 0;
    Map<Character, Integer> cnt = new HashMap<>(5);
    for (char c : word.toCharArray()) {
      if (vowel(c)) {
        cnt.merge(c, 1, Integer : : sum);
      } else {
        ++x;
      }
      while (x >= k && cnt.size() == 5) {
        char d = word.charAt(l++);
        if (vowel(d)) {
          if (cnt.merge(d, -1, Integer : : sum) == 0) {
            cnt.remove(d);
          }
        } else {
          --x;
        }
      }
      ans += l;
    }
    return ans;
  }
private
  boolean vowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
}

```

### Python

```python
class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int: def f(k: int) -> int: cnt = Counter() ans = l = x = 0 for c in word: if c in "aeiou": cnt[c] += 1 else: x += 1 while x >= k and len(cnt) == 5: d = word[l] if d in "aeiou": cnt[d] -= 1 if cnt[d] == 0: cnt . pop(d) else: x -= 1 l += 1 ans += l return ans return f(k) - f(k + 1)

```

### CPP

```cpp
class Solution {
public:
  int countOfSubstrings(string word, int k) {
    auto f = [&](int k) -> int {
      int ans = 0;
      int l = 0, x = 0;
      unordered_map<char, int> cnt;
      auto vowel = [&](char c) -> bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
      };
      for (char c : word) {
        if (vowel(c)) {
          cnt[c]++;
        } else {
          ++x;
        }
        while (x >= k && cnt.size() == 5) {
          char d = word[l++];
          if (vowel(d)) {
            if (--cnt[d] == 0) {
              cnt.erase(d);
            }
          } else {
            --x;
          }
        }
        ans += l;
      }
      return ans;
    };
    return f(k) - f(k + 1);
  }
};

```