Vowels of All Substrings
Problem
Given a string word, return the sum of the number of vowels (a,e,i,o,u) in every substring of word.
word = "aba"6def count_vowels(word):
n = len(word)
total = 0
for i, c in enumerate(word):
if c in 'aeiou':
total += (i + 1) * (n - i)
return totalfunction countVowels(word) {
const n = word.length;
let total = 0n;
for (let i = 0; i < n; i++) {
if ("aeiou".includes(word[i])) {
total += BigInt(i + 1) * BigInt(n - i);
}
}
return total;
}class Solution {
public long countVowels(String word) {
int n = word.length();
long total = 0;
for (int i = 0; i < n; i++) {
char c = word.charAt(i);
if ("aeiou".indexOf(c) >= 0) {
total += (long)(i + 1) * (n - i);
}
}
return total;
}
}long long countVowels(string word) {
int n = word.size();
long long total = 0;
for (int i = 0; i < n; i++) {
if (string("aeiou").find(word[i]) != string::npos) {
total += (long long)(i + 1) * (n - i);
}
}
return total;
}Explanation
Listing every substring and counting vowels would be too slow. Instead we use a contribution trick: ask how many substrings each single vowel belongs to, and add up those counts.
A character at index i is inside a substring when the substring starts at or before i and ends at or after i. There are i + 1 choices for the start (indices 0 through i) and n - i choices for the end. So the character sits in (i + 1) * (n - i) substrings.
We walk the string once. Whenever the character is a vowel, we add (i + 1) * (n - i) to the running total; non-vowels add nothing because they never count toward the answer.
Example: word = "aba" with n = 3. The a at index 0 contributes 1 * 3 = 3; the a at index 2 contributes 3 * 1 = 3; the b contributes 0. Total = 6.
Because each vowel's total presence is computed with one formula, we get the answer in a single O(n) pass instead of examining substrings one by one.