# Vowels of All Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/vowels-of-all-substrings)
Canonical: https://scaleengineer.com/dsa/problems/vowels-of-all-substrings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** String
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow)
---
## Problem
Given a string `word`, return _the **sum of the number of vowels** (_`'a'`, `'e'`_,_ `'i'`_,_ `'o'`_, and_ `'u'`_)_ _in every substring of_ `word`.

A **substring** is a contiguous (non-empty) sequence of characters within a string.

**Note:** Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

**Example 1:**

**Input:** word = "aba"
**Output:** 6
**Explanation:** 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6. 

**Example 2:**

**Input:** word = "abc"
**Output:** 3
**Explanation:** 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

**Example 3:**

**Input:** word = "ltcd"
**Output:** 0
**Explanation:** There are no vowels in any substring of "ltcd".

**Constraints:**

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

# Approaches
## Brute Force by Generating All Substrings
This approach involves generating every possible substring of the input `word`, and for each substring, counting the number of vowels it contains. The counts from all substrings are then summed up to get the final result.
**Time:** O(n^3) - where n is the length of the string `word`. We have three nested loops, each potentially iterating up to n times, leading to a cubic time complexity. · **Space:** O(1) - We only use a few variables to store the total count and loop indices, so the extra space is constant.
**Pros:** Very straightforward and easy to conceptualize and implement.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints (`n` up to 10^5).
### Explanation
The most straightforward way to solve this problem is to iterate through all possible start and end points to define a substring. We use two nested loops: the outer loop `i` selects the starting index, and the inner loop `j` selects the ending index. For each substring formed, we use a third loop to iterate through its characters and count the vowels. This count is added to a running total. While simple to understand, this method is computationally very expensive.

```java
class Solution {
    public long countVowels(String word) {
        long totalVowels = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Substring from i to j (inclusive)
                for (int k = i; k <= j; k++) {
                    char c = word.charAt(k);
                    if (isVowel(c)) {
                        totalVowels++;
                    }
                }
            }
        }
        return totalVowels;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
### Algorithm
- Initialize a `long` variable `totalVowels` to 0.
- Iterate with a loop for the start index `i` from 0 to `n-1` (where `n` is the length of the word).
- Inside this loop, iterate with another loop for the end index `j` from `i` to `n-1`.
- For the substring defined by `i` and `j`, iterate with a third loop from `k = i` to `j`.
- In the innermost loop, check if `word.charAt(k)` is a vowel. If it is, increment `totalVowels`.
- After all loops complete, return `totalVowels`.

## Optimized Substring Iteration
This approach improves upon the naive brute-force method by avoiding the third loop. Instead of recounting vowels for each substring from scratch, we can calculate the vowel count for a new, longer substring based on the count of the previous, shorter one.
**Time:** O(n^2) - where n is the length of `word`. The two nested loops lead to a quadratic time complexity. · **Space:** O(1) - Constant extra space is used for loop variables and counters.
**Pros:** More efficient than the O(n^3) approach.; Removes one level of nested loops.
**Cons:** Still too slow for the given constraints and will result in a 'Time Limit Exceeded' error.
### Explanation
We still use two nested loops to consider all substrings. The outer loop fixes the starting point `i` of the substrings. The inner loop extends the substring one character at a time, from `j = i` to `n-1`. For each starting point `i`, we maintain a `currentVowels` count. As we extend the substring by moving `j`, we update `currentVowels` based on the new character `word.charAt(j)`. The `currentVowels` for the substring `word[i...j]` is then added to the `totalVowels` sum in each step of the inner loop. This reduces the complexity from cubic to quadratic.

```java
class Solution {
    public long countVowels(String word) {
        long totalVowels = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            int currentVowels = 0;
            for (int j = i; j < n; j++) {
                if (isVowel(word.charAt(j))) {
                    currentVowels++;
                }
                totalVowels += currentVowels;
            }
        }
        return totalVowels;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
### Algorithm
- Initialize `totalVowels = 0`.
- Iterate with an outer loop `i` from `0` to `n-1` (start of substring).
- Initialize `currentVowels = 0` for substrings starting at `i`.
- Iterate with an inner loop `j` from `i` to `n-1` (end of substring).
- If `word[j]` is a vowel, increment `currentVowels`.
- Add the value of `currentVowels` to `totalVowels`.
- After the loops complete, return `totalVowels`.

## Mathematical Approach: Contribution of Each Character
This is the most efficient approach. Instead of iterating through substrings, we iterate through each character of the string and calculate how many substrings contain this character. If the character is a vowel, its total contribution is added to the final sum.
**Time:** O(n) - where n is the length of `word`. We perform a single pass through the string, and each step involves constant time operations. · **Space:** O(1) - We only use a few variables for the total sum, length, and loop index, requiring constant extra space.
**Pros:** Highly efficient and optimal with linear time complexity.; Passes all test cases within the time limit.
**Cons:** The logic is less intuitive than the brute-force approaches and requires a combinatorial insight.
### Explanation
The core idea is to change the perspective of the summation. Instead of `sum over all substrings (count of vowels in substring)`, we calculate `sum over all vowels (number of substrings containing this vowel)`. 

Consider a character `word[i]`. To form a substring that includes this character, the substring must start at an index `s` where `0 <= s <= i` and end at an index `e` where `i <= e < n`.
- The number of possible starting positions is `i + 1` (from index 0 to i).
- The number of possible ending positions is `n - i` (from index i to n-1).

Therefore, the total number of substrings containing the character at index `i` is `(i + 1) * (n - i)`. We can iterate through the string once. If `word[i]` is a vowel, we add this product to our total sum. Since the result can be large, we must use a 64-bit integer type (`long` in Java) for the sum and intermediate calculations.

```java
class Solution {
    public long countVowels(String word) {
        long totalVowels = 0;
        long n = word.length();
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                // A substring containing character at index i must start at or before i
                // and end at or after i.
                // Number of possible start indices: i + 1 (from 0 to i)
                // Number of possible end indices: n - i (from i to n-1)
                long occurrences = (long)(i + 1) * (n - i);
                totalVowels += occurrences;
            }
        }
        return totalVowels;
    }
}
```
### Algorithm
- Initialize `totalVowels = 0` and `n = word.length()`.
- Iterate through the string with index `i` from `0` to `n-1`.
- Check if the character `word[i]` is a vowel.
- If it is a vowel, calculate its contribution, which is the number of substrings it is a part of: `(i + 1) * (n - i)`.
- Add this contribution to `totalVowels`. Make sure to use 64-bit integers (`long`) for calculations to prevent overflow.
- Return `totalVowels`.

# Solutions
### JavaScript

```javascript
/** * @param {string} word * @return {number} */ var countVowels = function (
  word,
) {
  const n = word.length;
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    if ([" a ", " e ", " i ", " o ", " u "].includes(word[i])) {
      ans += (i + 1) * (n - i);
    }
  }
  return ans;
};

```

### Java

```java
class Solution {
public
  long countVowels(String word) {
    long ans = 0;
    for (int i = 0, n = word.length(); i < n; ++i) {
      char c = word.charAt(i);
      if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        ans += (i + 1L) * (n - i);
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def countVowels(self, word: str) -> int: n = len(word) return sum((i + 1) * (n - i) for i, c in enumerate(word) if c in 'aeiou')

```

### CPP

```cpp
class Solution {
public:
  long long countVowels(string word) {
    long long ans = 0;
    for (int i = 0, n = word.size(); i < n; ++i) {
      char c = word[i];
      if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        ans += (i + 1LL) * (n - i);
      }
    }
    return ans;
  }
};

```