Vowels of All Substrings
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible substring of the input word, and for each substring, counting the number of vowels it contains. The counts from all substrings are then summed up to get the final result.
Algorithm
- Initialize a
longvariabletotalVowelsto 0. - Iterate with a loop for the start index
ifrom 0 ton-1(wherenis the length of the word). - Inside this loop, iterate with another loop for the end index
jfromiton-1. - For the substring defined by
iandj, iterate with a third loop fromk = itoj. - In the innermost loop, check if
word.charAt(k)is a vowel. If it is, incrementtotalVowels. - After all loops complete, return
totalVowels.
Walkthrough
The most straightforward way to solve this problem is to iterate through all possible start and end points to define a substring. We use two nested loops: the outer loop i selects the starting index, and the inner loop j selects the ending index. For each substring formed, we use a third loop to iterate through its characters and count the vowels. This count is added to a running total. While simple to understand, this method is computationally very expensive.
class Solution { public long countVowels(String word) { long totalVowels = 0; int n = word.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Substring from i to j (inclusive) for (int k = i; k <= j; k++) { char c = word.charAt(k); if (isVowel(c)) { totalVowels++; } } } } return totalVowels; } private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}Complexity
Time
O(n^3) - where n is the length of the string `word`. We have three nested loops, each potentially iterating up to n times, leading to a cubic time complexity.
Space
O(1) - We only use a few variables to store the total count and loop indices, so the extra space is constant.
Trade-offs
Pros
Very straightforward and easy to conceptualize and implement.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints (
nup to 10^5).
This approach improves upon the naive brute-force method by avoiding the third loop. Instead of recounting vowels for each substring from scratch, we can calculate the vowel count for a new, longer substring based on the count of the previous, shorter one.
Algorithm
- Initialize
totalVowels = 0. - Iterate with an outer loop
ifrom0ton-1(start of substring). - Initialize
currentVowels = 0for substrings starting ati. - Iterate with an inner loop
jfromiton-1(end of substring). - If
word[j]is a vowel, incrementcurrentVowels. - Add the value of
currentVowelstototalVowels. - After the loops complete, return
totalVowels.
Walkthrough
We still use two nested loops to consider all substrings. The outer loop fixes the starting point i of the substrings. The inner loop extends the substring one character at a time, from j = i to n-1. For each starting point i, we maintain a currentVowels count. As we extend the substring by moving j, we update currentVowels based on the new character word.charAt(j). The currentVowels for the substring word[i...j] is then added to the totalVowels sum in each step of the inner loop. This reduces the complexity from cubic to quadratic.
class Solution { public long countVowels(String word) { long totalVowels = 0; int n = word.length(); for (int i = 0; i < n; i++) { int currentVowels = 0; for (int j = i; j < n; j++) { if (isVowel(word.charAt(j))) { currentVowels++; } totalVowels += currentVowels; } } return totalVowels; } private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}Complexity
Time
O(n^2) - where n is the length of `word`. The two nested loops lead to a quadratic time complexity.
Space
O(1) - Constant extra space is used for loop variables and counters.
Trade-offs
Pros
More efficient than the O(n^3) approach.
Removes one level of nested loops.
Cons
Still too slow for the given constraints and will result in a 'Time Limit Exceeded' error.
This is the most efficient approach. Instead of iterating through substrings, we iterate through each character of the string and calculate how many substrings contain this character. If the character is a vowel, its total contribution is added to the final sum.
Algorithm
- Initialize
totalVowels = 0andn = word.length(). - Iterate through the string with index
ifrom0ton-1. - Check if the character
word[i]is a vowel. - If it is a vowel, calculate its contribution, which is the number of substrings it is a part of:
(i + 1) * (n - i). - Add this contribution to
totalVowels. Make sure to use 64-bit integers (long) for calculations to prevent overflow. - Return
totalVowels.
Walkthrough
The core idea is to change the perspective of the summation. Instead of sum over all substrings (count of vowels in substring), we calculate sum over all vowels (number of substrings containing this vowel).
Consider a character word[i]. To form a substring that includes this character, the substring must start at an index s where 0 <= s <= i and end at an index e where i <= e < n.
- The number of possible starting positions is
i + 1(from index 0 to i). - The number of possible ending positions is
n - i(from index i to n-1).
Therefore, the total number of substrings containing the character at index i is (i + 1) * (n - i). We can iterate through the string once. If word[i] is a vowel, we add this product to our total sum. Since the result can be large, we must use a 64-bit integer type (long in Java) for the sum and intermediate calculations.
class Solution { public long countVowels(String word) { long totalVowels = 0; long n = word.length(); for (int i = 0; i < n; i++) { char c = word.charAt(i); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { // A substring containing character at index i must start at or before i // and end at or after i. // Number of possible start indices: i + 1 (from 0 to i) // Number of possible end indices: n - i (from i to n-1) long occurrences = (long)(i + 1) * (n - i); totalVowels += occurrences; } } return totalVowels; }}Complexity
Time
O(n) - where n is the length of `word`. We perform a single pass through the string, and each step involves constant time operations.
Space
O(1) - We only use a few variables for the total sum, length, and loop index, requiring constant extra space.
Trade-offs
Pros
Highly efficient and optimal with linear time complexity.
Passes all test cases within the time limit.
Cons
The logic is less intuitive than the brute-force approaches and requires a combinatorial insight.
Solutions
Solution
/** * @param {string} word * @return {number} */ var countVowels = function ( word,) { const n = word.length; let ans = 0; for (let i = 0; i < n; ++i) { if ([" a ", " e ", " i ", " o ", " u "].includes(word[i])) { ans += (i + 1) * (n - i); } } return ans;};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; }}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')class Solution {public: long long countVowels(string word) { long long ans = 0; for (int i = 0, n = word.size(); i < n; ++i) { char c = word[i]; if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { ans += (i + 1LL) * (n - i); } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.