How to Solve Vowels of All Substrings

The optimal solution counts vowels by calculating how many substrings each vowel contributes to, avoiding brute-force substring generation. By using state transition dynamic programming, each character's impact is tracked in a single pass. This reduces time complexity dramatically while ensuring accuracy for large strings.

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

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.

How GhostInterview Helps

• Automatically applies state transition DP logic to count vowel contributions efficiently.
• Highlights edge cases and large input handling where naive substring methods fail.
• Provides step-by-step verification for each character's impact on substring vowel totals.

Topic Pages

• Math
• String
• Dynamic Programming
• Combinatorics

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.