2063. 所有子字符串中的元音
https://leetcode.cn/problems/vowels-of-all-substrings/description/
题目:
给你一个字符串 word ，返回 word 的所有子字符串中 元音的总数 ，元音是指 'a'、'e'、'i'、'o' 和 'u' 。
子字符串 是字符串中一个连续（非空）的字符序列。
注意：由于对 word 长度的限制比较宽松，答案可能超过有符号 32 位整数的范围。计算时需当心。1 <= word.length <= 105
word 由小写英文字母组成
思路1（贡献法）
考虑每个元音字母的贡献。
把字符串长度记作 \(n\) ，考虑字符串中位置 \(i\) （0-based）上的字符 word[i]。
如果 word[i] 是元音字母（a,e,i,o,u），那么它出现在多少个子字符串中？
任何包含位置 \(i\) 的子字符串，左端点可以选在 \([0, i]\) 中的任意位置（共 \(i+1\) 种），右端点可以选在 \([i, n-1]\) 中的任意位置（共 \(n-i\) 种）。因此包含这个字符的子字符串一共有
种。于是只要把所有元音位置的这个值累加起来就是答案。
时间复杂度 \(O(n)\) ，只需一次线性遍历；空间复杂度 \(O(1)\) 。注意答案可能很大，使用 64 位整型 long long 存储。
例子验证
字符串 "aba"， \(n=3\) ：
- i=0，
'a'： \((0+1)*(3-0)=1*3=3\) - i=1，
'b'：不是元音，跳过 - i=2，
'a'： \((2+1)*(3-2)=3*1=3\)
总和 = 6，与你枚举的所有子字符串里的元音总数一致。
C++（OI 风格，详细注释）
#include <bits/stdc++.h>
using namespace std;/** 题目：所有子字符串中的元音* 思路：对每个位置 i，如果是元音，则其贡献为 (i+1)*(n-i)。* 注意：使用 long long 存储答案，防止溢出。** 代码风格：OI 风格，简洁、高效，注释详细。*/inline bool isVowel(char c) {// 只处理小写字母 —— 题目保证输入是小写return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string word;if (!(cin >> word)) return 0; // 读取输入字符串long long ans = 0;long long n = (long long)word.size(); // 转为 long long 以便后续乘法安全for (long long i = 0; i < n; ++i) {if (isVowel(word[(size_t)i])) {// 位置 i 的贡献为 (i+1) * (n-i)// 都用 long long 计算，避免中间溢出ans += (i + 1) * (n - i);}}cout << ans << '\n';return 0;
}
类似的「每个位置贡献法」可以解决很多子串/区间计数的问题
解法二（DP ）
把所有以位置 \(i\) 为右端点的子字符串看成一组，记 \(dp[i]\) 为“所有以 \(i\) 为右端点的子字符串中，元音的总数”。
考虑从 \(i-1\) 扩展到 \(i\) ：
- 新加入的右端为 \(i\) 的子字符串有 \(i+1\) 个（左端可选 0..i）。
- 对于每个左端 \(k\) （ \(0\le k\le i\) ），子串 \(s[k..i]\) 的元音数 = 子串 \(s[k..i-1]\) 的元音数 + （若 \(s[i]\) 是元音则 +1 否则 +0）。
- 把所有左端加起来，得到：
（其中 \([s[i]\text{ 是元音}]\) 为 1 或 0）
题目要的就是 所有子字符串中元音的总数，这正好是对每个右端点的贡献求和：
这个 DP 与我们之前每个位置直接计算 \((i+1)(n-i)\) 的方法等价，但 DP 思路更容易迁移到类似题型。时间复杂度 \(O(n)\) ，可以把空间压到 \(O(1)\) 。
举例（快速验证）
字符串 "aba"：
- \(i=0\) ：dp0 = 0 + 1*1 = 1
- \(i=1\) ：dp1 = dp0 + 2*0 = 1
- \(i=2\) ：dp2 = dp1 + 3*1 = 4
ans = 1+1+4 = 6，正确。
C++（OI 风格，详注）
#include <bits/stdc++.h>
using namespace std;/** DP 版解法：* dp[i] 表示所有以 i 为右端点的子串中，元音的总数。* 递推： dp[i] = dp[i-1] + (i+1) * isVowel(s[i])* 最终答案为 sum(dp[i]) (i 从 0 到 n-1)。** 时间：O(n)，空间：O(1)（只保存当前 dp 和累加和）*/inline bool isVowel(char c) {// 题目保证小写字母，这里只判断小写元音return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s;if (!(cin >> s)) return 0;long long n = (long long)s.size();long long dp_prev = 0; // dp[i-1]long long ans = 0; // 最终答案：sum(dp[i])for (long long i = 0; i < n; ++i) {// 如果 s[i] 是元音，则它对所有以 i 为右端点的子串贡献 (i+1)long long contrib = isVowel(s[(size_t)i]) ? (i + 1) : 0;long long dp_i = dp_prev + contrib; // dp[i]ans += dp_i; // 累加到答案里dp_prev = dp_i; // 更新用于下一轮}cout << ans << '\n';return 0;
}