Vowels of All Substrings solution and explanation
8 more videos on this problem
Vowels of All Substrings | LeetCode Weekly contest 266 | DSAAditya Rajiv · 10:36 · 5K views
2063. Vowels of All Substrings (Leetcode Medium)Programming Live with Larry · 7:22 · 1K views
#faang interview question series| Leetcode #2063 | Vowels of all substrings|Reverse lookup techniqueProgramming Pathshala · 16:42 · 1K views
Vowels of all Substrings | EPAM Question & Solution | Edystedyst · 22:19 · 995 views
Leetcode 2063. Vowels of All SubstringsElite Code · 19:18 · 460 views
2063 Vowels of All SubstringsMath Geeks · 7:11 · 326 views
Leetcode 2063 | Java Solution |Coding with Arpan. · 5:23 · 268 views
LeetCode Problem | Vowels of all Substrings 🔥💯🙌🏻Learning with Ilsa · 6:15 · 92 views
LeetCode 2063: Vowels of All SubstringsAlitaCode · 26:49 · 4 views
The problem
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.
def is_vowel(c):
return c in 'aeiou'
def sum_vowels_of_substrings(word):
n = len(word)
result = 0
for i in range(n):
for j in range(i, n):
for k in range(i, j + 1):
if is_vowel(word[k]):
result += 1
return result
word = 'aba'
result = sum_vowels_of_substrings(word)
print(result)public class VowelSubstrings {
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static long sumVowelsOfSubstrings(String word) {
int n = word.length();
long result = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
if (isVowel(word.charAt(k))) {
result++;
}
}
}
}
return result;
}
public static void main(String[] args) {
String word = "aba";
System.out.println(sumVowelsOfSubstrings(word));
}
}#include <iostream>
#include <string>
bool is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
long sum_vowels_of_substrings(const std::string &word) {
int n = word.size();
long result = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
if (is_vowel(word[k])) {
result++;
}
}
}
}
return result;
}
int main() {
std::string word = "aba";
long result = sum_vowels_of_substrings(word);
std::cout << result << std::endl;
return 0;
}function isVowel(c) {
return 'aeiou'.includes(c);
}
function sumVowelsOfSubstrings(word) {
const n = word.length;
let result = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
for (let k = i; k <= j; k++) {
if (isVowel(word[k])) {
result++;
}
}
}
}
return result;
}
const word = "aba";
console.log(sumVowelsOfSubstrings(word));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
long sum_vowels_of_substrings(char *word) {
int n = strlen(word);
long result = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
if (is_vowel(word[k])) {
result++;
}
}
}
}
return result;
}
int main() {
char word[] = "aba";
long result = sum_vowels_of_substrings(word);
printf("%ld\n", result);
return 0;
}using System;
class VowelSubstrings {
static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
static long SumVowelsOfSubstrings(string word) {
int n = word.Length;
long result = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
if (IsVowel(word[k])) {
result++;
}
}
}
}
return result;
}
static void Main() {
string word = "aba";
Console.WriteLine(SumVowelsOfSubstrings(word));
}
}This Python function computes the sum of vowels in all substrings by checking each possible substring.
Time Complexity: O(n^3) because of three loops.
Space Complexity: O(1).
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.
def is_vowel(c):
return c in 'aeiou'
def sum_vowels_of_substrings(word):
n = len(word)
result = 0
for i in range(n):
if is_vowel(word[i]):
result += (i + 1) * (n - i)
return result
word = 'aba'
result = sum_vowels_of_substrings(word)
print(result)public class VowelSubstrings {
public static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public static long sumVowelsOfSubstrings(String word) {
int n = word.length();
long result = 0;
for (int i = 0; i < n; i++) {
if (isVowel(word.charAt(i))) {
result += (long)(i + 1) * (n - i);
}
}
return result;
}
public static void main(String[] args) {
String word = "aba";
System.out.println(sumVowelsOfSubstrings(word));
}
}#include <iostream>
#include <string>
bool is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
long sum_vowels_of_substrings(const std::string &word) {
int n = word.size();
long result = 0;
for (int i = 0; i < n; i++) {
if (is_vowel(word[i])) {
result += (long)(i + 1) * (n - i);
}
}
return result;
}
int main() {
std::string word = "aba";
long result = sum_vowels_of_substrings(word);
std::cout << result << std::endl;
return 0;
}function isVowel(c) {
return 'aeiou'.includes(c);
}
function sumVowelsOfSubstrings(word) {
const n = word.length;
let result = 0;
for (let i = 0; i < n; i++) {
if (isVowel(word[i])) {
result += (i + 1) * (n - i);
}
}
return result;
}
const word = "aba";
console.log(sumVowelsOfSubstrings(word));#include <stdio.h>
#include <string.h>
int is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
long sum_vowels_of_substrings(char *word) {
int n = strlen(word);
long result = 0;
for (int i = 0; i < n; i++) {
if (is_vowel(word[i])) {
result += (long)(i + 1) * (n - i);
}
}
return result;
}
int main() {
char word[] = "aba";
long result = sum_vowels_of_substrings(word);
printf("%ld\n", result);
return 0;
}using System;
class VowelSubstrings {
static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
static long SumVowelsOfSubstrings(string word) {
int n = word.Length;
long result = 0;
for (int i = 0; i < n; i++) {
if (IsVowel(word[i])) {
result += (long)(i + 1) * (n - i);
}
}
return result;
}
static void Main() {
string word = "aba";
Console.WriteLine(SumVowelsOfSubstrings(word));
}
}This Python method efficiently calculates the number of vowels by leveraging each vowel's influence across all substrings.
Time Complexity: O(n).
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).
function countVowels(word: string): number {
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;
}func countVowels(word string) (ans int64) {
for i, c := range word {
if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
ans += int64((i + 1) * (len(word) - i))
}
}
return
}impl Solution {
pub fn count_vowels(word: String) -> i64 {
let n = word.len() as i64;
word.chars()
.enumerate()
.filter(|(_, c)| "aeiou".contains(*c))
.map(|(i, _)| (i as i64 + 1) * (n - i as i64))
.sum()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: |
| Optimized Contribution Approach | Time Complexity: |
| Enumerate Contribution | – |
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 |
Frequently asked questions
Is Vowels of All Substrings easy or hard?
The problem is rated Medium because the brute force idea is straightforward but inefficient. The challenge is recognizing that each vowel contributes to many substrings and applying the combinatorial formula to compute that contribution in O(n) time.
Vowels of All Substrings Python/Java solution
In Python or Java, iterate through the string and check if each character is one of 'a', 'e', 'i', 'o', or 'u'. If it is, add (i + 1) * (n - i) to a running total. This implementation runs in O(n) time and uses constant extra space.
How to solve Vowels of All Substrings in O(n)?
Iterate through the string once. Whenever a character is a vowel, compute how many substrings include that position using the formula (i + 1) * (n - i). Add this value to the total. This works because each vowel contributes to every substring that starts before it and ends after it.
What is the best approach for Vowels of All Substrings?
The optimal approach is the contribution counting technique. For each vowel at index i in a string of length n, calculate how many substrings include it using (i + 1) * (n - i). Summing these contributions for all vowels produces the total count in O(n) time and O(1) space.
Is Vowels of All Substrings asked at Google/Amazon/Meta?
Problems based on substring contribution counting and combinatorics appear frequently in interviews at companies like Google, Amazon, and Meta. The pattern of counting element contributions instead of generating all substrings is a common optimization interviewers expect candidates to recognize.
What data structure is used in Vowels of All Substrings?
The optimal solution does not require complex data structures. A simple loop over the string and a constant-time vowel check using a set or conditional comparison is enough. The main idea relies on combinatorics rather than storage structures.
What is the time complexity of Vowels of All Substrings?
The optimal solution runs in O(n) time with O(1) space by scanning the string once and computing each vowel's contribution. A brute force substring enumeration approach takes O(n^2) time because it generates and evaluates every substring.