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.

#2063

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

所有子字符串中的元音

给你一个字符串 word ，返回 word 的所有子字符串中元音的总数，元音是指 'a' 、 'e' 、 'i' 、 'o' 和 'u' 。子字符串是字符串中一个连续（非空）的字符序列。注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。示…

数学字符串动态规划组合数学

题目描述

给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。

子字符串 是字符串中一个连续（非空）的字符序列。

注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。

示例 1：

输入：word = "aba"
输出：6
解释：
所有子字符串是："a"、"ab"、"aba"、"b"、"ba" 和 "a" 。
- "b" 中有 0 个元音
- "a"、"ab"、"ba" 和 "a" 每个都有 1 个元音
- "aba" 中有 2 个元音
因此，元音总数 = 0 + 1 + 1 + 1 + 1 + 2 = 6 。

示例 2：

输入：word = "abc"
输出：3
解释：
所有子字符串是："a"、"ab"、"abc"、"b"、"bc" 和 "c" 。
- "a"、"ab" 和 "abc" 每个都有 1 个元音
- "b"、"bc" 和 "c" 每个都有 0 个元音
因此，元音总数 = 1 + 1 + 1 + 0 + 0 + 0 = 3 。

示例 3：

输入：word = "ltcd"
输出：0
解释："ltcd" 的子字符串均不含元音。

示例 4：

输入：word = "noosabasboosa"
输出：237
解释：所有子字符串中共有 237 个元音。

提示：

1 <= word.length <= 10⁵
word 由小写英文字母组成

lightbulb

解题思路

方法一：枚举贡献

我们可以枚举字符串的每个字符 $\textit{word}[i]$ ，如果 $\textit{word}[i]$ 是元音字母，那么 $\textit{word}[i]$ 一共在 $(i + 1) \times (n - i)$ 个子字符串中出现，将这些子字符串的个数累加即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $\textit{word}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

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')

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2019 解出数学表达式的学生分数 #2147 分隔长廊的方案数 #1916 统计为蚁群构筑房间的不同顺序