# Count of Substrings Containing Every Vowel and K Consonants II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii
**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 <= 2 * 105`
* `word` consists only of lowercase English letters.
* `0 <= k <= word.length - 5`

# Approaches
## Brute Force
The most straightforward way to solve this problem is to check every single substring of the input `word`. We can generate all substrings, and for each one, we verify if it contains all five vowels ('a', 'e', 'i', 'o', 'u') and exactly `k` consonants.
**Time:** O(N³), where N is the length of the string. There are O(N²) substrings, and checking each one takes O(N) time. This is too slow for the given constraints. · **Space:** O(1), as the set for vowels will hold at most 5 elements.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will not pass the time limits for the given constraints.; Redundant computations as information about overlapping substrings is not reused.
### Explanation
This approach involves a triply nested loop structure. The outer two loops define the start (`i`) and end (`j`) indices of a substring. The third, inner loop (or a function call that implies a loop) iterates over this substring `word[i..j]` to count its vowels and consonants. A set is used to keep track of the unique vowels encountered to ensure all five are present. If a substring satisfies both conditions (5 unique vowels and `k` consonants), we increment our result counter.

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

    public long beautifulSubstrings(String word, int k) {
        long count = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check substring word[i..j]
                Set<Character> vowels = new HashSet<>();
                int consonants = 0;
                for (int l = i; l <= j; l++) {
                    char c = word.charAt(l);
                    if (isVowel(c)) {
                        vowels.add(c);
                    } else {
                        consonants++;
                    }
                }
                if (vowels.size() == 5 && consonants == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Generate all possible substrings of the `word` using two nested loops. The outer loop `i` iterates from `0` to `n-1` (start of the substring), and the inner loop `j` iterates from `i` to `n-1` (end of the substring).
2. For each substring `word[i..j]`, create a helper function to check if it meets the criteria.
3. The helper function will iterate through the characters of the substring.
4. Inside the helper function, use a frequency map or a set to count the number of distinct vowels and a separate counter for consonants.
5. After iterating through the substring, check if the number of distinct vowels is exactly 5 and the number of consonants is exactly `k`.
6. If both conditions are met, increment a global counter.
7. Return the global counter after checking all substrings.

## Optimized Brute Force
We can optimize the brute-force approach by avoiding the repeated scanning of substrings. Instead of re-calculating the vowel and consonant counts for each substring from scratch, we can fix the starting point of a substring and extend it one character at a time, updating the counts incrementally.
**Time:** O(N²), where N is the length of the string. We have two nested loops. This will time out given the constraints. · **Space:** O(1), as the vowel set stores at most 5 elements.
**Pros:** More efficient than the naive O(N³) brute-force approach.; Still relatively easy to understand.
**Cons:** Still too slow for the given constraints as it has a quadratic time complexity.
### Explanation
This method reduces one level of looping from the naive brute-force approach. We iterate through all possible starting positions `i` of a substring. For each `i`, we iterate from `j = i` to the end of the string. We maintain the counts of distinct vowels and consonants for the substring `word[i..j]`. When we extend the substring to `word[i..j+1]`, we just need to account for the new character `word.charAt(j+1)`. This avoids the third loop for checking the substring property, bringing the complexity down.

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

    public long beautifulSubstrings(String word, int k) {
        long count = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            Set<Character> vowels = new HashSet<>();
            int consonants = 0;
            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (isVowel(c)) {
                    vowels.add(c);
                } else {
                    consonants++;
                }
                if (vowels.size() == 5 && consonants == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Use two nested loops. The outer loop `i` fixes the starting index of the substring.
2. The inner loop `j` extends the substring by one character at a time, starting from `i`.
3. For each starting index `i`, initialize a vowel set and a consonant counter.
4. As the inner loop pointer `j` moves from `i` to `n-1`, update the vowel set and consonant count for the current substring `word[i..j]` based on the character `word.charAt(j)`.
5. After each update, check if the vowel set size is 5 and the consonant count is `k`.
6. If the conditions are met, increment the total count of beautiful substrings.
7. Repeat for all starting indices `i`.

## Sliding Window with Three Pointers
The most efficient solution uses a sliding window technique with multiple pointers. The main idea is to fix the right endpoint of a substring and efficiently count the number of valid left endpoints. A substring is valid if it satisfies two conditions: containing all five vowels and having exactly `k` consonants. We can find the range of valid start indices for each condition separately and then find their intersection.
**Time:** O(N), where N is the length of the string. Each of the four pointers (`j`, `p_vowel`, `p_k`, `p_k_minus_1`) traverses the string at most once. · **Space:** O(1), as the `vowelCounts` array has a fixed size of 26.
**Pros:** Highly efficient with linear time complexity.; Optimal solution that will pass for large inputs.
**Cons:** The logic is complex and involves careful state management of three interacting sliding windows.; Can be tricky to implement correctly without off-by-one errors.
### Explanation
We iterate through the string with a right pointer `j` from `0` to `n-1`. For each `j`, we maintain three left pointers: `p_k`, `p_k_minus_1`, and `p_vowel`. These pointers define the start of windows that satisfy certain conditions up to `j`.

- `p_k`: The start of the shortest suffix of `word[0..j]` with at most `k` consonants.
- `p_k_minus_1`: The start of the shortest suffix of `word[0..j]` with at most `k-1` consonants.
- `p_vowel`: The first index `i` such that `word[i..j]` does *not* contain all 5 vowels.

For a fixed `j`, any starting index `i` in the range `[p_k, p_k_minus_1 - 1]` will result in a substring `word[i..j]` with exactly `k` consonants. Any starting index `i < p_vowel` will result in a substring with all 5 vowels. We need to count the number of indices `i` that satisfy both conditions. This corresponds to the length of the intersection of the valid ranges, which is `max(0, min(p_vowel, p_k_minus_1) - p_k)`. By summing these counts for each `j`, we get the total number of beautiful substrings.

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

    public long beautifulSubstrings(String s, int k) {
        long ans = 0;
        int n = s.length();

        int p_vowel = 0;
        int p_k = 0;
        int p_k_minus_1 = 0;

        int[] vowelCounts = new int[26];
        int distinctVowels = 0;
        int consonants_k = 0;
        int consonants_k_minus_1 = 0;

        for (int j = 0; j < n; j++) {
            char char_j = s.charAt(j);

            if (isVowel(char_j)) {
                if (vowelCounts[char_j - 'a'] == 0) {
                    distinctVowels++;
                }
                vowelCounts[char_j - 'a']++;
            } else {
                consonants_k++;
                consonants_k_minus_1++;
            }

            while (consonants_k > k) {
                if (!isVowel(s.charAt(p_k))) {
                    consonants_k--;
                }
                p_k++;
            }

            while (consonants_k_minus_1 > k - 1) {
                if (!isVowel(s.charAt(p_k_minus_1))) {
                    consonants_k_minus_1--;
                }
                p_k_minus_1++;
            }

            while (distinctVowels == 5) {
                char char_pv = s.charAt(p_vowel);
                if (isVowel(char_pv)) {
                    vowelCounts[char_pv - 'a']--;
                    if (vowelCounts[char_pv - 'a'] == 0) {
                        distinctVowels--;
                    }
                }
                p_vowel++;
            }

            ans += Math.max(0, Math.min(p_vowel, p_k_minus_1) - p_k);

            if (distinctVowels < 5 && p_vowel > 0) {
                char char_pv_prev = s.charAt(p_vowel - 1);
                if (isVowel(char_pv_prev)) {
                    if (vowelCounts[char_pv_prev - 'a'] == 0) {
                        distinctVowels++;
                    }
                    vowelCounts[char_pv_prev - 'a']++;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
1. The core idea is to iterate through the string with a right pointer `j` and, for each `j`, count how many valid left pointers `i` exist.
2. A substring `word[i..j]` is valid if it has all 5 vowels and exactly `k` consonants.
3. We can rephrase the consonant condition: the number of consonants is at most `k` AND not at most `k-1`.
4. We use three left pointers: `p_vowel`, `p_k`, and `p_k_minus_1`, which slide along with the right pointer `j`.
5. For each `j`:
    a. `p_k` is advanced such that the window `[p_k, j]` has at most `k` consonants.
    b. `p_k_minus_1` is advanced such that `[p_k_minus_1, j]` has at most `k-1` consonants. This means any valid start `i` for the consonant condition must be in the range `[p_k, p_k_minus_1 - 1]`.
    c. `p_vowel` is advanced such that `[p_vowel-1, j]` is the shortest suffix of `[0, j]` containing all 5 vowels. This means any valid start `i` for the vowel condition must be `i < p_vowel`.
6. The number of valid start indices `i` for the current `j` is the size of the intersection of these two ranges: `[p_k, p_k_minus_1 - 1]` and `[0, p_vowel - 1]`.
7. The number of valid `i`'s is `max(0, min(p_vowel, p_k_minus_1) - p_k)`. Add this to the total answer.
8. All pointers only move forward, leading to a linear time complexity.

# Solutions
### Java

```java
class Solution {
public
  long countOfSubstrings(String word, int k) {
    return f(word, k) - f(word, k + 1);
  }
private
  long f(String word, int k) {
    long 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';
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countOfSubstrings(string word, int k) {
    auto f = [&](int k) -> long long {
      long long 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);
  }
};

```

### 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)

```