Watch 9 video solutions for Vowels of All Substrings, a medium level problem involving Math, String, Dynamic Programming. This walkthrough by Aditya Rajiv has 5,875 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Given a lowercase string word, count how many vowels appear across every possible substring. Each substring contributes the number of vowels it contains, and the goal is to sum that count for all substrings.
Approach 1: Brute Force Substring Enumeration (O(n²) time, O(1) space)
The straightforward solution generates every possible substring and counts the vowels inside it. Use two nested loops: the outer loop selects the starting index and the inner loop extends the substring to the right. While extending, maintain a running vowel count so you don't re-scan the substring each time. Every extension contributes the current vowel count to the final answer. This approach demonstrates the underlying mechanics clearly, but with n up to large values, the O(n²) runtime becomes too slow.
Approach 2: Vowel Contribution Counting (O(n) time, O(1) space)
The optimal solution avoids generating substrings entirely. Instead, compute how many substrings include each character. For a character at index i in a string of length n, the number of substrings containing it equals (i + 1) * (n - i). The term (i + 1) represents the number of possible starting positions before or at i, while (n - i) represents the possible ending positions after or at i. If the character is a vowel, it contributes exactly this many counts to the total answer. Iterate through the string once, check if the current character belongs to the vowel set, and add its contribution. This transforms the problem into a simple linear scan.
This technique relies on combinatorial counting rather than substring construction. Problems that involve counting contributions across all subarrays or substrings often use the same idea. The method appears frequently in string analysis problems and combinatorial counting tasks related to math and combinatorics. Some interview discussions also connect it conceptually to prefix accumulation patterns seen in dynamic programming.
Recommended for interviews: Interviewers expect the contribution counting approach. The brute force method shows you understand how substrings work, but the O(n) combinatorial solution demonstrates stronger algorithmic insight. Recognizing that each vowel participates in multiple substrings—and counting them directly—is the key optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n²) | O(1) | Useful for understanding substring generation or when constraints are very small |
| Vowel Contribution Counting | O(n) | O(1) | Best for large inputs and expected interview solution |