Vowels of All Substrings - Solution & Explanation
Problem Statement
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 <= 105wordconsists of lowercase English letters.
Approach Overview
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 1: Brute Force Approach
This approach considers all possible substrings and counts the vowels in each one. It is straightforward but computationally expensive due to its O(n^2) complexity.
This implementation checks all possible substrings of the input string word and counts the vowels in each substring.
Complexity
Time Complexity: O(n^3) due to three nested loops.
Space Complexity: O(1), no additional space needed.
Approach 2: Optimized Contribution Approach
For this optimized approach, consider each vowel's contribution to different substrings directly. If a character is a vowel at position i, it can appear in (i + 1) starting positions and (n - i) ending positions, totaling (i + 1) * (n - i) substrings. Sum these contributions for each vowel in the given string.
This optimized C implementation calculates the contribution of each vowel directly without generating all substrings, significantly reducing computational work.
Complexity
Time Complexity: O(n) as we iterate through the string once.
Space Complexity: O(1).
Approach 3: Enumerate Contribution
We can enumerate each character word[i] in the string. If word[i] is a vowel, then word[i] appears in (i + 1) times (n - i) substrings. We sum up the counts of these substrings.
The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: |
| Optimized Contribution Approach | Time Complexity: |
| Enumerate Contribution | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Vowels of All Substrings | LeetCode Weekly contest 266 | DSA • Aditya Rajiv • 5,991 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Vowels of All Substrings easy or hard?
Vowels of All Substrings Python/Java solution
How to solve Vowels of All Substrings in O(n)?
What is the best approach for Vowels of All Substrings?
Is Vowels of All Substrings asked at Google/Amazon/Meta?
What data structure is used in Vowels of All Substrings?
What is the time complexity of Vowels of All Substrings?
Ready to solve this problem?
Practice Vowels of All Substrings with our built-in code editor and test cases.
Practice on FleetCode