Abstract / Summary

Count total vowels across all substrings of a given string by considering each vowel's contribution based on its position.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (80k+ submissions).

Typical patterns to solve this problem:

• Combinatorics
• Dynamic Programming
• Math
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method countVowels. The method receives a string word and returns an integer representing the total number of vowel appearances across all possible substrings of the input. The algorithm iterates once over the characters of the string, identifies vowel positions, and for each vowel computes the number of substrings that contain it by multiplying the count of possible prefix lengths with the count of possible suffix lengths. The accumulated sum is then returned.

Core Logic

The method begins by initializing an accumulator named result to zero. This variable holds the running total of vowel contributions.

result = 0

A for loop enumerates the characters of word, exposing both the index i and the character c. Enumeration is crucial because the position of each character determines how many substrings can include it.

for i, c in enumerate(word):

Inside the loop, a membership test checks whether the current character belongs to the set of lowercase English vowels "aeiou". The test is performed using the in operator, which runs in constant time for a short literal string.

if c in "aeiou":

When a vowel is found, two quantities are derived:

• left - the number of possible starting positions for a substring that ends at or after the vowel. Because a substring can start at any index from 0 up to i, the count equals i + 1.
• right - the number of possible ending positions for a substring that starts at or before the vowel. Since the substring can end at any index from i to len(word) - 1, the count equals len(word) - i.

left  = i + 1          # prefix
right = len(word) - i  # suffix

The product left * right yields the total number of distinct substrings that contain the vowel at position i. This product is added to result.

result += left * right # all combinations of prefix and suffix

After the loop finishes, the method returns the accumulated value.

return result

The entire flow can be visualized as a single pass that transforms each vowel into a contribution based on its combinatorial reach within the string.

Edge Cases Handled

The algorithm gracefully handles several boundary conditions without additional code:

• Empty string - The loop body never executes, leaving result at its initial value of 0. The method correctly returns 0, reflecting that no substrings exist.
• String without vowels - The if condition never succeeds, so result remains 0. This correctly indicates that no vowel appears in any substring.
• String consisting solely of vowels - Every character triggers the contribution calculation. For a string of length n, the total equals the sum of i+1 times n-i for each index i, which matches the combinatorial expectation.
• Single-character strings - When the character is a vowel, left and right both evaluate to 1, and the method returns 1. If the character is a consonant, the method returns 0. Both outcomes are correct.
• Mixed case input - The membership test checks only lowercase vowels. Consequently, uppercase vowels are ignored, which aligns with the function’s implicit contract of handling lowercase input only.

Performance Characteristics

The implementation exhibits several performance-friendly traits:

• Linear traversal - By iterating once over the input string, the algorithm runs in time proportional to the length of word. No nested loops or recursive calls are introduced.
• Constant-time operations inside the loop - The vowel check, arithmetic calculations, and accumulator update each execute in O(1) time. The use of a literal string for the vowel set avoids the overhead of constructing a data structure on each iteration.
• Minimal memory footprint - Apart from the input string and a few integer variables (result, i, left, right), the method does not allocate additional containers. This keeps auxiliary memory usage low.
• Avoidance of substring generation - Rather than materializing each possible substring, the algorithm computes the contribution analytically. This eliminates the combinatorial explosion that would arise from explicit substring creation, preserving both speed and memory.

Overall, the code delivers an efficient solution for counting vowel occurrences across all substrings by leveraging combinatorial insight and a straightforward single-pass design.

Imagine you have a long, colorful train made of alphabet blocks. This code is like a little helper that wants to count how many special windows appear in every possible piece of that train. The special windows are the vowels, which are the letters a, e, i, o, and u.

The code looks at each letter in the train one by one. When it finds a vowel, it stops to see how many different parts of the train include that specific block. It counts how many ways it can pick a piece that starts before the vowel and ends after the vowel. To do this, it counts how many blocks are to the left of the vowel and how many blocks are to the right. By multiplying those two numbers, the helper finds every possible trip that goes through that vowel. It adds all those little trips together until it has checked every single block in the train.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python				TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++	JS	Java		Python		Go	Rust	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	suxrobGM						C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality