LeetCode 2063 - Vowels of All Substrings

LeetCode Problem 2063

Difficulty: 🟡 Medium
Topics: Math, String, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem asks us to compute the total number of vowels that appear across every possible substring of a given string.

A substring is any contiguous sequence of characters. For a string of length n, there are n * (n + 1) / 2 total substrings. For each substring, we count how many vowels it contains, then sum all of those counts together.

The vowels are the lowercase English letters:

a, e, i, o, u

The input is a single string word consisting only of lowercase English letters. The output is a single integer representing the total vowel contribution across all substrings.

The constraints are important:

• 1 <= word.length <= 10^5

A string of length 100000 can generate about 5 * 10^9 substrings, which is far too many to enumerate directly. This immediately tells us that any brute force approach that explicitly generates substrings will be too slow.

Another important detail is that the answer may exceed a 32-bit signed integer. This means we must use larger integer types:

• Python handles large integers automatically
• In Go, we should use int64

There are several edge cases worth identifying early:

• A string with no vowels, such as "ltcd", should return 0
• A string where every character is a vowel produces very large totals
• A single-character string should still work correctly
• Very large inputs require an efficient linear-time solution
• Repeated vowels can contribute many times across overlapping substrings

The key challenge is avoiding explicit substring generation while still counting all vowel occurrences correctly.

Approaches

Brute Force Approach

The most straightforward solution is to generate every possible substring and count how many vowels each substring contains.

For every starting index i, we can extend the substring to every ending index j, forming word[i:j+1]. Then we count the vowels inside that substring and add the result to the final answer.

This approach is correct because it literally follows the definition of the problem. Every substring is examined exactly once, and the number of vowels inside it is computed directly.

However, the performance is extremely poor.

There are O(n^2) substrings. Counting vowels inside each substring takes up to O(n) time, leading to a total complexity of O(n^3).

Even with optimizations such as prefix sums, the best brute-force style solution still requires iterating through all substrings, resulting in O(n^2) time. Since n can be 100000, this is still far too slow.

Optimal Approach

The key insight is that we do not need to generate substrings individually.

Instead, we can determine how many substrings include each vowel character.

Suppose a vowel appears at index i.

To form a substring containing this character:

• The substring can start at any index from 0 to i
• The substring can end at any index from i to n - 1

Therefore:

• Number of possible starting positions = i + 1
• Number of possible ending positions = n - i

So the total number of substrings containing this character is:

$(i+1)(n-i)$

Each of those substrings contributes exactly 1 vowel count from this specific character.

So whenever we encounter a vowel, we simply add:

$(i+1)(n-i)$

to the answer.

This transforms the problem into a simple linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(1)	Explicitly examines substrings
Optimal	O(n)	O(1)	Counts contribution of each vowel directly

Algorithm Walkthrough

1. Initialize a variable total_vowels to store the final answer.
2. Create a set containing all vowels:

{'a', 'e', 'i', 'o', 'u'}

A set allows constant-time membership checking. 3. Iterate through the string using index i and character ch. 4. For each character, check whether it is a vowel. 5. If the character is a vowel, compute how many substrings include it.

The substring:

• Can start anywhere from index 0 through i
• Can end anywhere from index i through n - 1

Therefore:

contribution = (i + 1) * (n - i)

6. Add this contribution to total_vowels.
7. Continue until the entire string has been processed.
8. Return total_vowels.

Why it works

Every substring contribution can be decomposed by character position.

For a vowel at index i, every substring that includes index i contributes exactly one vowel count from that character. The number of such substrings is precisely:

$(i+1)(n-i)$

By summing this value for every vowel position, we count every vowel occurrence in every substring exactly once. No substring is missed, and no contribution is double-counted.

Python Solution

class Solution:
    def countVowels(self, word: str) -> int:
        n = len(word)
        vowels = {'a', 'e', 'i', 'o', 'u'}

        total_vowels = 0

        for index, char in enumerate(word):
            if char in vowels:
                total_vowels += (index + 1) * (n - index)

        return total_vowels

The implementation begins by storing the string length in n, since we use it repeatedly during contribution calculations.

A set of vowels is created for efficient membership testing. Using a set ensures each lookup operates in average constant time.

The algorithm then scans the string once using enumerate, which provides both the index and character.

Whenever the current character is a vowel, we calculate how many substrings contain that position. The expression:

(index + 1) * (n - index)

counts all valid start and end combinations for substrings containing the character.

That contribution is added directly to total_vowels.

Finally, the accumulated answer is returned.

Because Python integers automatically expand to arbitrary precision, no special overflow handling is necessary.

Go Solution

func countVowels(word string) int64 {
    n := len(word)

    vowels := map[byte]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
    }

    var totalVowels int64 = 0

    for i := 0; i < n; i++ {
        if vowels[word[i]] {
            totalVowels += int64(i+1) * int64(n-i)
        }
    }

    return totalVowels
}

The Go solution follows the same logic as the Python version.

One important difference is integer handling. Since the answer may exceed 32-bit integer limits, we explicitly use int64 for the result and during multiplication.

The string is indexed directly using word[i], which returns a byte. Therefore, the vowel lookup map also uses byte keys.

Go does not have Python's arbitrary-precision integers, so careful type conversion is necessary during arithmetic operations.

Worked Examples

Example 1

Input: "aba"

String length:

n = 3

Index	Character	Is Vowel	Contribution Formula	Contribution	Running Total
0	a	Yes	(0 + 1) × (3 - 0)	1 × 3 = 3	3
1	b	No	-	0	3
2	a	Yes	(2 + 1) × (3 - 2)	3 × 1 = 3	6

Final answer:

6

The contributing substrings are:

"a", "ab", "aba", "ba", "a"

The total vowel count across them is 6.

Example 2

Input: "abc"

Index	Character	Is Vowel	Contribution Formula	Contribution	Running Total
0	a	Yes	(0 + 1) × (3 - 0)	1 × 3 = 3	3
1	b	No	-	0	3
2	c	No	-	0	3

Final answer:

3

Example 3

Input: "ltcd"

Index	Character	Is Vowel	Contribution	Running Total
0	l	No	0	0
1	t	No	0	0
2	c	No	0	0
3	d	No	0	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The string is scanned exactly once
Space	O(1)	Only a small fixed-size vowel set/map is used

The algorithm processes each character exactly one time, and every operation inside the loop is constant time. Therefore, the runtime grows linearly with the length of the string.

The extra memory usage remains constant regardless of input size because the vowel collection always contains exactly five characters.

Test Cases

solution = Solution()

# Provided examples
assert solution.countVowels("aba") == 6          # basic mixed string
assert solution.countVowels("abc") == 3          # one vowel at beginning
assert solution.countVowels("ltcd") == 0         # no vowels

# Single character cases
assert solution.countVowels("a") == 1            # single vowel
assert solution.countVowels("z") == 0            # single consonant

# All vowels
assert solution.countVowels("aeiou") == 35       # every character contributes

# Repeated vowels
assert solution.countVowels("aaa") == 10         # overlapping vowel contributions

# Mixed characters
assert solution.countVowels("leetcode") == 58    # typical mixed input

# Large repeated pattern
assert solution.countVowels("u" * 1000) > 0      # stress test with many vowels

# No vowels large input
assert solution.countVowels("b" * 1000) == 0     # stress test without vowels

# Alternating vowels and consonants
assert solution.countVowels("ababab") == 28      # multiple distributed vowels

Test Case Summary

Test	Why
"aba"	Validates overlapping substring contributions
"abc"	Tests single vowel contribution
"ltcd"	Ensures zero-vowel handling
"a"	Smallest valid vowel input
"z"	Smallest valid consonant input
"aeiou"	Tests all-vowel scenario
"aaa"	Verifies repeated vowel accumulation
"leetcode"	Realistic mixed input
"u" * 1000	Stress test with many contributions
"b" * 1000	Stress test with no contributions
"ababab"	Tests alternating character patterns

Edge Cases

Strings With No Vowels

A string such as "ltcd" contains no vowels at all. A buggy implementation might accidentally count consonants or mishandle empty contribution calculations.

This implementation handles the case naturally because contributions are only added when the current character belongs to the vowel set. If no vowel is found, the total remains 0.

Strings Where Every Character Is a Vowel

Inputs like "aaaaa" produce very large totals because every character contributes to many substrings. This can expose integer overflow issues in languages with fixed-width integers.

The Python solution handles this automatically with arbitrary-precision integers. The Go implementation explicitly uses int64 to safely store large values.

Very Large Inputs

The maximum input size is 100000. Any approach that generates substrings explicitly will time out or consume excessive memory.

This implementation avoids substring construction entirely. It processes the string in a single pass and uses only constant extra space, making it efficient even at maximum constraints.

Single-Character Strings

A one-character string is the smallest valid input and is easy to mishandle with off-by-one errors.

For example:

• "a" should return 1
• "b" should return 0

The contribution formula:

$(i+1)(n-i)$

works correctly even when n = 1, so these edge cases are handled automatically.