Vowels of All Substrings — Solution in Python, Java & C++
Vowels of All Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Vowels of All Substrings is a medium coding problem on strings, dynamic programming and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string word, consider every one of its non-empty substrings (contiguous runs of characters). For each substring count its vowels ('a', 'e', 'i', 'o' and 'u'), and return the sum of those counts over all substrings.
Substrings at different positions are counted separately even if they read the same.
The length bound below is tightened from the original problem so that the answer always fits in a 32-bit signed integer.
Example 1
Input: word = "kairo"
Output: 22
Explanation: The `a` at index 1 lies in 2 × 4 = 8 substrings, the `i` at index 2 in 3 × 3 = 9 and the `o` at index 4 in 5 × 1 = 5.
Example 2
Input: word = "ae"
Output: 4
Explanation: `"a"`, `"e"` and `"ae"` hold 1, 1 and 2 vowels.
Example 3
Input: word = "xyz"
Output: 0
Constraints
1 <= word.length <= 2000word consists of lowercase English letters
Hints for Vowels of All Substrings
Hint 1
Instead of looking at each substring, flip it around: how many substrings contain a given position?
Hint 2
A substring containing index
istarts somewhere in0..iand ends somewhere ini..n-1.Hint 3
So the vowel at index
iis counted(i + 1) × (n - i)times. Sum that over the vowels.
How to solve Vowels of All Substrings
Count by contribution: the character at index i belongs to exactly (i + 1) × (n - i) substrings, so each vowel adds that many to the total.
Approach
- Let
nbe the length ofword. - For each index
iholding a vowel, add(i + 1) × (n - i)to the answer. - Return the sum (computed in 64-bit arithmetic where the language needs it).
Why it works
The requested sum counts pairs (substring, vowel position inside it). Grouping those pairs by the vowel instead of by the substring gives the same total. A substring word[l..r] contains i exactly when 0 <= l <= i and i <= r <= n - 1, which is (i + 1) choices for l times (n - i) choices for r.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Enumerating substrings is O(n²) or worse; the contribution formula is linear.
- In the original problem
nreaches 10^5 and the sum needs 64 bits; heren <= 2000keeps it below 2^31, but accumulate in a wide type anyway. yis not a vowel here.
Reference solution
Python
def countVowels(word: str) -> int:
n = len(word)
total = 0
for i, ch in enumerate(word):
if ch in "aeiou":
total += (i + 1) * (n - i)
return totalJava
public static int countVowels(String word) {
int n = word.length();
long total = 0;
for (int i = 0; i < n; i++) {
if ("aeiou".indexOf(word.charAt(i)) >= 0) total += (long) (i + 1) * (n - i);
}
return (int) total;
}C++
int countVowels(string word) {
long long n = word.size(), total = 0;
for (long long i = 0; i < n; i++) {
char c = word[i];
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') total += (i + 1) * (n - i);
}
return (int)total;
}JavaScript
var countVowels = function(word) {
var n = word.length, total = 0;
for (var i = 0; i < n; i++) {
if ("aeiou".indexOf(word[i]) >= 0) total += (i + 1) * (n - i);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming