#2063

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Vowels of All Substrings

Compute the total number of vowels in all substrings of a given string using efficient state transition dynamic programming techniques.

math string dynamic programming combinatorics

Problem Statement

Given a lowercase English string word, return the sum of all vowels present in every possible substring of word. Vowels are defined as 'a', 'e', 'i', 'o', and 'u'.

A substring is any contiguous sequence of characters from word. The total sum may exceed 32-bit integer limits, so take care with large inputs and avoid generating all substrings explicitly.

Examples

Example 1

Input: word = "aba"

Output: 6

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

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

There are no vowels in any substring of "ltcd".

Constraints

1 <= word.length <= 105
word consists of lowercase English letters.

Solution Approach

Count contributions of each vowel

Iterate through the string and for each vowel, compute how many substrings include it. The count for word[i] is (i + 1) * (n - i) where n is word.length. Sum these contributions for the final answer.

Use state transition dynamic programming

Track a running total where each step adds the contribution of the current character based on whether it is a vowel. This pattern leverages state transitions to avoid recomputing substring counts repeatedly.

Single pass aggregation

Maintain a cumulative sum of vowel contributions in one traversal. This ensures O(n) time and O(1) extra space, preventing memory issues from storing all substrings and respecting constraints for large strings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed once. Space complexity is O(1) beyond input storage, as we only track running totals without storing substrings.

What Interviewers Usually Probe

Expect recognition of the state transition dynamic programming pattern for substring aggregation.
Check if candidate avoids generating all substrings explicitly due to high constraints.
Look for understanding that each vowel contributes to multiple substrings multiplicatively.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all substrings leading to TLE for large strings.
Forgetting to count a vowel in all substrings it participates in, missing multiplicative contributions.
Not using long or 64-bit integer for the sum, causing overflow in large inputs.

Follow-up variants

Count consonants in all substrings using a similar state transition approach.
Return the maximum number of vowels in any single substring instead of total sum.
Compute sum of vowels only for substrings of a fixed length k using the same pattern.

FAQ

How does the state transition DP pattern work in Vowels of All Substrings?

Each vowel's contribution is calculated by the number of substrings it appears in, allowing accumulation without generating all substrings, following a dynamic state update per character.

Why can't I generate all substrings for this problem?

The string can be up to 10^5 characters, making substring generation O(n^2) and causing time and memory overflow. Counting contributions per character avoids this.

What is the time complexity of the optimal solution?

It is O(n) because each character is visited once, and the multiplicative contributions are computed on the fly.

Do I need special integer types for large strings?

Yes, using 64-bit integers or long types is necessary to prevent overflow when summing contributions for large inputs.

Can this approach be adapted for other substring counting problems?

Yes, any problem where character contributions multiply over substrings, such as counting consonants or vowels of fixed lengths, can use this state transition pattern.

terminal

Solution

Solution 1: Enumerate Contribution

We can enumerate each character $\textit{word}[i]$ in the string. If $\textit{word}[i]$ is a vowel, then $\textit{word}[i]$ appears in $(i + 1) \times (n - i)$ substrings. We sum up the counts of these substrings.

1

2

3

4

class Solution:
    def countVowels(self, word: str) -> int:
        n = len(word)
        return sum((i + 1) * (n - i) for i, c in enumerate(word) if c in 'aeiou')

Continue Practicing

#2019 the score of students solving math expression #2147 number of ways to divide a long corridor #1916 count ways to build rooms in an ant colony