{x}
blog image

Vowels of All Substrings

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.

Solution Explanation

This problem asks to find the sum of vowels across all substrings of a given string. A naive approach would generate all substrings and count vowels, but this is inefficient (O(n³)). A more optimal approach leverages the observation that each vowel contributes to the count based on its position.

Core Idea:

Consider a vowel at index i in the string. This vowel appears in substrings starting from index 0 up to i and ending from i up to the end of the string. Thus, the number of substrings containing the vowel at index i is (i + 1) * (n - i), where n is the string's length.

Algorithm:

  1. Iterate: Traverse the input string word.
  2. Check for Vowel: For each character, check if it's a vowel ('a', 'e', 'i', 'o', 'u').
  3. Calculate Contribution: If it's a vowel at index i, add (i + 1) * (n - i) to the total count. The (i+1) accounts for substrings starting at or before index i, and (n-i) accounts for substrings ending at or after index i.
  4. Return Total: After iterating through all characters, return the accumulated count.

Code Explanation (Python3)

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')
  • n = len(word): Gets the length of the input string.
  • sum(...): This is a concise way to accumulate the contributions of each vowel.
  • (i + 1) * (n - i): Calculates the number of substrings containing the vowel at index i.
  • for i, c in enumerate(word): Iterates through the string with index i and character c.
  • if c in 'aeiou': Checks if the character is a vowel.

Code Explanation (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;
    }
}

This Java code follows the same logic. Note the use of long ans to handle potentially large sums, and explicit vowel checking.

Time and Space Complexity Analysis

Time Complexity: O(n), where n is the length of the string. We iterate through the string once.

Space Complexity: O(1). We use only a constant amount of extra space.

The provided solutions in other languages (C++, Go, TypeScript) all implement the same efficient algorithm with minor syntactic differences. They all achieve a linear time complexity.