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 <= 105word consists of lowercase English letters.In #2063 Vowels of All Substrings, the key challenge is counting how many times vowels appear across all possible substrings of a given string. A naive approach would generate every substring and count vowels inside each one, but this leads to O(n^2) or worse time complexity.
A more efficient idea is to think in terms of character contribution. Instead of examining every substring explicitly, determine how many substrings include a specific character. If the character is a vowel, its contribution equals the number of substrings that contain that position. By analyzing how many choices exist for the left and right boundaries of substrings around an index, you can compute its total impact directly.
This mathematical observation transforms the problem into a single pass through the string. The optimized solution leverages simple arithmetic and avoids extra data structures, achieving linear time while using constant space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (Generate all substrings) | O(n^2) | O(1) |
| Contribution / Combinatorics Approach | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Since generating substrings is not an option, can we count the number of substrings a vowel appears in?
How much does each vowel contribute to the total sum?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems based on substring contributions and combinatorial counting are common in FAANG-style interviews. This question tests pattern recognition, mathematical reasoning, and the ability to optimize from brute force to linear time.
Combinatorics helps determine how many substrings include a given index. By counting possible left and right boundaries around a character, you can directly compute how often that character appears across all substrings.
No complex data structure is required. A simple string traversal with a quick vowel check (using a set or conditional checks) is enough, since the main logic relies on combinatorics rather than storage.
The optimal approach uses a contribution-based idea. Instead of generating all substrings, calculate how many substrings include each character and add its contribution if it is a vowel. This allows the problem to be solved in a single linear pass.