Vowels of All Substrings

Problem Description

Given a string word, return the sum of the number of vowels (i.e., 'a', 'e', 'i', 'o', and 'u') in every substring of word. A substring is a contiguous (non-empty) sequence of characters within a string. Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

Key Insights

• Each character in the string contributes to multiple substrings.
• Vowels have a specific contribution based on their position in the string.
• Using combinatorial reasoning can help avoid generating all substrings explicitly, thus optimizing the solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can calculate the contribution of each vowel character in the string to the total count of vowels in all substrings. For each vowel at position i, we can determine how many substrings include this vowel based on its position.

The number of substrings that include the vowel can be calculated as:

1. The number of ways to choose a starting point for the substring, which can be any index from 0 to i.
2. The number of ways to choose an endpoint for the substring, which can be any index from i to the end of the string.

Thus, the total number of substrings that include the vowel at position i is (i + 1) * (n - i), where n is the length of the string. We sum this contribution for all vowels in the string.

Code Solutions