Vowels of All Substrings - Practice Coding Problems

Vowels of All Substrings - 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.

Input & Output

Example 1 — Basic Case

$ Input: word = "aba"

› Output: 6

💡 Note: Substrings are: "a" (1 vowel), "ab" (1 vowel), "aba" (2 vowels), "b" (0 vowels), "ba" (1 vowel), "a" (1 vowel). Total: 1+1+2+0+1+1 = 6

Example 2 — No Vowels

$ Input: word = "abc"

› Output: 3

💡 Note: Substrings are: "a" (1), "ab" (1), "abc" (1), "b" (0), "bc" (0), "c" (0). Total: 1+1+1+0+0+0 = 3

Example 3 — All Vowels

$ Input: word = "aei"

› Output: 9

💡 Note: Each position contributes: a at pos 0: (0+1)*(3-0)=3, e at pos 1: (1+1)*(3-1)=4, i at pos 2: (2+1)*(3-2)=3. Total: 3+4+2 = 9

Constraints

1 ≤ word.length ≤ 10⁵
word consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with vowels and consonants

Process

Count vowels across all possible substrings

Output

Total sum of all vowel occurrences

Key Takeaway

🎯 Key Insight: Each vowel at position i contributes to (i+1)×(n-i) substrings - use math instead of generating all substrings

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that instead of generating all substrings, we can calculate how many times each vowel contributes to the final sum. Each character at position i appears in exactly (i+1) × (n-i) substrings. Best approach uses mathematical formula with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Generate all substrings and count vowels in each
Mathematical Formula	O(n)	O(1)	Calculate each character's contribution across all substrings

Brute Force — Algorithm Steps

Generate all possible substrings using nested loops
For each substring, count the number of vowels
Sum up all vowel counts from all substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings using nested loops

Count Vowels

For each substring, count vowels individually

Sum Results

Add all vowel counts together

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

long long solution(char* word) {
    long long total = 0;
    int n = strlen(word);
    
    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])) {
                    total++;
                }
            }
        }
    }
    
    return total;
}

int main() {
    char word[100001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    long long result = solution(word);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops to generate n² substrings, each taking O(n) time to count vowels

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track counts, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler