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).
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;};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.