# Count Vowel Substrings of a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-vowel-substrings-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/count-vowel-substrings-of-a-string
**Data structures:** Hash Table, String
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [PayPal](https://scaleengineer.com/companies/paypal), [Snowflake](https://scaleengineer.com/companies/snowflake), [Commvault](https://scaleengineer.com/companies/commvault)
---
## Problem
A **substring** is a contiguous (non-empty) sequence of characters within a string.

A **vowel substring** is a substring that **only** consists of vowels (`'a'`, `'e'`, `'i'`, `'o'`, and `'u'`) and has **all five** vowels present in it.

Given a string `word`, return _the number of **vowel substrings** in_ `word`.

**Example 1:**

**Input:** word = "aeiouu"
**Output:** 2
**Explanation:** The vowel substrings of word are as follows (underlined):
- "**aeiou**u"
- "**aeiouu**"

**Example 2:**

**Input:** word = "unicornarihan"
**Output:** 0
**Explanation:** Not all 5 vowels are present, so there are no vowel substrings.

**Example 3:**

**Input:** word = "cuaieuouac"
**Output:** 7
**Explanation:** The vowel substrings of word are as follows (underlined):
- "c**uaieuo**uac"
- "c**uaieuou**ac"
- "c**uaieuoua**c"
- "cu**aieuo**uac"
- "cu**aieuou**ac"
- "cu**aieuoua**c"
- "cua**ieuoua**c"

**Constraints:**

* `1 <= word.length <= 100`
* `word` consists of lowercase English letters only.

# Approaches
## Brute-Force Enumeration
This approach involves generating every possible substring of the input `word` and then checking if each substring meets the criteria of a "vowel substring". A substring is valid if it contains only vowels and includes all five vowels ('a', 'e', 'i', 'o', 'u').
**Time:** O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and for each of the O(N^2) substrings, we iterate through it to check its validity, which can take up to O(N) time. · **Space:** O(N), where N is the length of the string. This is because `word.substring(i, j + 1)` can create a new string of length up to N. The `HashSet` uses O(1) space as there are only 5 vowels.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient due to the cubic time complexity.; It might be too slow for larger inputs, though it passes for the given constraints (N <= 100).
### Explanation
The algorithm iterates through all possible start and end points to define a substring. For each generated substring, it performs a two-part check. First, it verifies that every character in the substring is a vowel. If this holds, it then checks if the set of unique vowels in the substring contains all five required vowels. This is the most straightforward but also the least efficient way to solve the problem.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countVowelSubstrings(String word) {
        int count = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = word.substring(i, j + 1);
                if (isVowelSubstring(sub)) {
                    count++;
                }
            }
        }
        return count;
    }

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

    private boolean isVowelSubstring(String s) {
        Set<Character> vowels = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (!isVowel(c)) {
                return false;
            }
            vowels.add(c);
        }
        return vowels.size() == 5;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Use two nested loops to generate all substrings. The outer loop with index `i` determines the start of the substring, and the inner loop with index `j` determines the end.
*   For each substring `s = word.substring(i, j + 1)`:
*   Check if `s` is a valid vowel substring using a helper function `isVowelSubstring(s)`.
*   The helper function `isVowelSubstring(s)` will:
    *   Iterate through each character of `s`. If any character is a consonant, return `false`.
    *   Use a `HashSet` to keep track of the unique vowels present in `s`.
    *   After checking all characters, if the size of the `HashSet` is exactly 5, return `true`. Otherwise, return `false`.
*   If `isVowelSubstring(s)` returns `true`, increment the `count`.
*   After checking all substrings, return `count`.

## Optimized Brute-Force
This approach improves upon the brute-force method by avoiding the creation of new substrings and re-checking characters repeatedly. Instead of generating and checking each substring from scratch, we can check the properties of substrings starting at a fixed position `i` in a single, more efficient pass.
**Time:** O(N^2). We have two nested loops. The operations inside the inner loop (HashSet add, checking size) take constant time on average. · **Space:** O(1). The `HashSet` used to track found vowels stores at most 5 distinct characters, which is constant space.
**Pros:** More efficient than the O(N^3) approach.; Avoids expensive substring creation in each iteration.
**Cons:** Still not the most optimal solution as it has a quadratic time complexity.
### Explanation
We use nested loops where the outer loop fixes the starting point `i` of a substring. The inner loop extends the substring by one character at a time, moving from `i` to the end of the string. For each starting point `i`, we maintain a `HashSet` of vowels. As we extend the substring to the right with index `j`, we add the new character to the set. If we encounter a consonant, we know that no further extension from `i` will result in a valid vowel-only substring, so we can break the inner loop and move to the next starting position. If the character is a vowel, we add it to our set and check if the set's size has reached 5. If it has, we've found a valid vowel substring and increment our counter.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countVowelSubstrings(String word) {
        int count = 0;
        int n = word.length();
        Set<Character> vowels = new HashSet<>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');

        for (int i = 0; i < n; i++) {
            Set<Character> foundVowels = new HashSet<>();
            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (!vowels.contains(c)) {
                    break; // Not a vowel, so break the inner loop
                }
                foundVowels.add(c);
                if (foundVowels.size() == 5) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Iterate through the string with an outer loop using index `i` from 0 to N-1. This `i` will be the starting point of our potential substrings.
*   Inside the outer loop, initialize a `HashSet` to store the vowels encountered for substrings starting at `i`.
*   Start an inner loop with index `j` from `i` to N-1. This `j` will be the ending point.
*   For each character `word.charAt(j)`:
    *   Check if it's a vowel. If it's a consonant, then no further substring starting at `i` and ending at or after `j` can be a vowel-only substring. So, `break` the inner loop.
    *   If it's a vowel, add it to the `HashSet`.
    *   Check if the size of the `HashSet` is 5. If it is, we have found a valid vowel substring `word.substring(i, j + 1)`, so we increment `count`.

## Sliding Window with Inclusion-Exclusion
The most efficient approach uses a sliding window technique. The core idea is to first recognize that any valid vowel substring must be entirely contained within a contiguous block of vowels. Consonants act as natural boundaries. We can therefore solve the problem for each vowel-only block and sum the results. To count substrings with *exactly* 5 distinct vowels within a block, we use a clever trick: calculate the number of substrings with *at most* 5 distinct vowels and subtract the number of substrings with *at most* 4 distinct vowels.
**Time:** O(N). The `atMost` function processes each character of the string at most twice (once by the `right` pointer, once by the `left` pointer). Since we call it twice, the complexity is O(N) + O(N) = O(N). · **Space:** O(1). The frequency map for vowels uses constant space as there are at most 5 keys.
**Pros:** Optimal time complexity.; Efficient and scalable for larger inputs.
**Cons:** The logic is more complex to understand and implement compared to brute-force approaches.
### Explanation
This method provides a linear-time solution. We iterate through the string with a pointer `i`. If `word.charAt(i)` is a consonant, it marks the end of a potential vowel-only segment. We then calculate the number of valid substrings within the segment from the last consonant (or the beginning of the string) to `i-1`. This calculation is done by calling a helper function `atMost(k)` which counts substrings with at most `k` distinct vowels. The final count for the segment is `atMost(5) - atMost(4)`. The `atMost(k)` helper function itself uses a sliding window (`left`, `right` pointers) and a frequency map to efficiently count the substrings in linear time.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countVowelSubstrings(String word) {
        int totalVowelSubstrings = 0;
        int lastConsonant = -1;
        for (int i = 0; i < word.length(); i++) {
            if (!isVowel(word.charAt(i))) {
                lastConsonant = i;
            }
            // For a window ending at i, we need a starting point j such that
            // word[j...i] is a valid vowel substring.
            // This is hard to count directly. Instead, we use an inclusion-exclusion principle.
            // We find a window [j, i] that contains only vowels.
            // Then count substrings in word[j...i] with exactly 5 vowels.
            // This is equal to (count of substrings with at most 5 vowels) - (count of substrings with at most 4 vowels).
        }
        return atMost(word, 5) - atMost(word, 4);
    }

    private int atMost(String s, int k) {
        int count = 0;
        int left = 0;
        Map<Character, Integer> freq = new HashMap<>();
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (!isVowel(c)) {
                // Reset window if a consonant is found
                left = right + 1;
                freq.clear();
                continue;
            }

            freq.put(c, freq.getOrDefault(c, 0) + 1);

            while (freq.size() > k) {
                char leftChar = s.charAt(left);
                freq.put(leftChar, freq.get(leftChar) - 1);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }
            // For the window [left, right], all substrings ending at right are valid.
            // The number of such substrings is (right - left + 1).
            count += (right - left + 1);
        }
        return count;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
### Algorithm
*   The main problem is broken down: count substrings with exactly 5 distinct vowels that only contain vowels.
*   This can be rephrased as: `(count of substrings with at most 5 distinct vowels) - (count of substrings with at most 4 distinct vowels)`.
*   We first iterate through the input string to identify contiguous blocks of vowels. Consonants act as separators.
*   For each vowel-only block, we apply a helper function, `countAtMostK(word, start, end, k)`, twice: once for `k=5` and once for `k=4`.
*   The `countAtMostK(word, start, end, k)` function uses a sliding window:
    *   Initialize `count = 0`, `left = start`, and a frequency map for vowels.
    *   Iterate from `start` to `end` with a `right` pointer.
    *   Add `word.charAt(right)` to the window and update the frequency map and the count of distinct vowels.
    *   If the number of distinct vowels exceeds `k`, shrink the window from the left by incrementing the `left` pointer and updating the map until the condition is met again.
    *   For each `right`, the number of valid substrings ending at `right` is `right - left + 1`. Add this to the total `count`.
*   The result for a vowel block is `countAtMostK(block, 5) - countAtMostK(block, 4)`.
*   Sum these results for all vowel blocks to get the final answer.

# Solutions
### Java

```java
class Solution {
public
  int countVowelSubstrings(String word) {
    int n = word.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      Set<Character> t = new HashSet<>();
      for (int j = i; j < n; ++j) {
        char c = word.charAt(j);
        if (!isVowel(c)) {
          break;
        }
        t.add(c);
        if (t.size() == 5) {
          ++ans;
        }
      }
    }
    return ans;
  }
private
  boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countVowelSubstrings(string word) {
    int ans = 0;
    int n = word.size();
    for (int i = 0; i < n; ++i) {
      unordered_set<char> t;
      for (int j = i; j < n; ++j) {
        char c = word[j];
        if (!isVowel(c))
          break;
        t.insert(c);
        ans += t.size() == 5;
      }
    }
    return ans;
  }
  bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
};

```

### Python

```python
class Solution:
    def countVowelSubstrings(self, word: str) -> int: n = len(word) s = set('aeiou') return sum(set(word[i: j]) == s for i in range(n) for j in range(i + 1, n + 1))

```