题目考点
这道题的核心考点其实非常明确，主要有这几个：
- 字符串遍历
- 分类统计（元音 / 辅音）
- 找规律，避免暴力枚举
- 时间复杂度意识
这题最关键的不是“怎么把所有子串列出来”，而是要意识到：题目数据很大，不能真的去生成所有子串。
因为 len(S) 最多可到 10^6，如果暴力做，肯定超时。
审题
输入是什么
输入只有一行，一个大写字符串 S。
例如：
BANANA
输出是什么
输出赢家名字和分数，中间空格隔开：
Stuart 12
如果两个人分数一样，就输出：
Draw
题目到底在比什么
- Kevin 只能拿“以元音开头”的子串得分
- Stuart 只能拿“以辅音开头”的子串得分
而且这里的“得分”不是“不同子串的种类数”，而是：
这个子串在原字符串里出现几次，就加几分。
不过，这道题真正巧妙的地方是：
你不需要真的把子串一个个造出来再统计出现次数。
思路提示
先不要急着写代码，先抓住一个最重要的问题：
我们到底在统计什么？
如果一个位置 i 上的字符是元音，那么从这个位置开始的所有子串，都归 Kevin。
如果这个位置 i 上的字符是辅音，那么从这个位置开始的所有子串，都归 Stuart。
所以问题就变成了：
“从某个位置开始，一共有多少个子串？”
你可以先自己想一想：
- 下标是
i - 字符串长度是
n - 从
i开始，结尾可以选哪些位置？
答案是：
从 i 开始，可以一直到最后一个字符结束，所以一共有：
n - i
个子串。
这就是整道题的突破口。
完整设计思路
第一步：不要暴力生成所有子串
很多初学者一看到“子串”就会想到双重循环、三重循环去切片。
比如：
- 枚举起点
- 枚举终点
- 生成子串
- 判断归 Kevin 还是 Stuart
- 再统计次数
这个思路在小数据下能做，但这题不行，因为字符串长度最大 10^6，暴力一定超时。
第二步：换个角度看“得分”
我们不去看“具体子串长什么样”，只看：
这个位置作为起点，能贡献多少分。
假设字符串长度是 n，当前位置是 i。
从 i 开始的子串有：
S[i:i+1]
S[i:i+2]
S[i:i+3]
...
S[i:n]
一共就是 n - i 个。
所以：
- 如果
S[i]是元音，这n - i分全给 Kevin - 如果
S[i]是辅音，这n - i分全给 Stuart
第三步：遍历整个字符串，把每个位置的贡献加起来
于是我们只需要做一件事：
从左到右遍历字符串，对于每个位置：
- 算出它能产生多少个子串：
n - i - 看这个字符是元音还是辅音
- 把这些分数加到对应玩家身上
第四步：最后比较大小
- Kevin 大于 Stuart，输出
Kevin 分数 - Stuart 大于 Kevin，输出
Stuart 分数 - 相等输出
Draw
代码实现
下面是适合初学者理解的基础写法：
def minion_game(string):
vowels = "AEIOU"
kevin_score = 0
stuart_score = 0
n = len(string)
for i in range(n):
point = n - i
if string[i] in vowels:
kevin_score += point
else:
stuart_score += point
if kevin_score > stuart_score:
print("Kevin", kevin_score)
elif stuart_score > kevin_score:
print("Stuart", stuart_score)
else:
print("Draw")
如果平台模板是这样的：
if __name__ == '__main__':
s = input()
minion_game(s)
那直接配合上面的函数就可以运行。
运行演示
我们用样例 BANANA 手动走一遍。
字符串：
BANANA
长度 n = 6
第 0 个位置：B
- 是辅音，归 Stuart
- 从这里开始的子串有：
- B
- BA
- BAN
- BANA
- BANAN
- BANANA
- 一共
6 - 0 = 6个
所以：
Stuart = 6
Kevin = 0
第 1 个位置：A
- 是元音，归 Kevin
- 从这里开始的子串有
6 - 1 = 5个
所以：
Kevin = 5
Stuart = 6
第 2 个位置：N
- 是辅音
- 贡献
6 - 2 = 4
所以：
Stuart = 10
Kevin = 5
第 3 个位置：A
- 是元音
- 贡献
6 - 3 = 3
所以：
Kevin = 8
Stuart = 10
第 4 个位置：N
- 是辅音
- 贡献
6 - 4 = 2
所以：
Stuart = 12
Kevin = 8
第 5 个位置：A
- 是元音
- 贡献
6 - 5 = 1
所以：
Kevin = 9
Stuart = 12
最后结果：
Stuart 12
这和题目样例完全一致。
方法总结
这道题非常值得记住，因为它是典型的“表面是子串题，实际是找规律计数题”。
以后遇到类似题目，可以先这样想：
识别信号 1：数据很大
只要你看到长度能到 10^5、10^6，就要立刻警惕：
不能暴力枚举所有子串、所有子序列、所有区间。
识别信号 2：题目在问“有多少个”而不是“具体是什么”
这种题常常可以从“逐个生成对象”转成“直接计算贡献”。
识别信号 3：按位置贡献，而不是按结果分类
这题最关键的思维转变就是：
不是去统计每个具体子串，而是统计每个起点位置能贡献多少分。
这类题的通用下手方式
以后碰到字符串 / 数组计数题，可以先问自己 3 个问题：
- 我真的需要把所有结果都造出来吗？
- 一个位置能贡献多少答案？
- 能不能把“枚举对象”改成“累计贡献”？
如果能这么改，复杂度往往会从 O(n^2) 降到 O(n)。
易错点回顾
1. 把题目理解成“不同子串数量”
错。
这题不是统计不同子串有多少种，而是统计所有可能子串的出现次数总和。
2. 真的去切片生成子串
比如写成：
for i in range(n):
for j in range(i + 1, n + 1):
sub = string[i:j]
这样会超时。
3. 忘了 Y 不是元音
题目里明确说了，元音只有：
AEIOU
4. 写成 return，而题目要求 print
这题通常平台模板要求你在函数里直接打印结果，不是返回字符串。
这个一定要看清模板。
练习
下面给你一道同类型的小练习，先不要急着看答案，先自己按“位置贡献”的思路想一遍。
练习题
给你一个只包含大写字母的字符串 S。
现在规定：
- 甲玩家拿所有“以下标为偶数的位置开头”的子串分数
- 乙玩家拿所有“以下标为奇数的位置开头”的子串分数
仍然是一个子串出现一次记 1 分。
请输出赢家和分数；如果平局输出 Draw。
例如：
输入：
ABCDE
你先自己想：
- 每个位置能贡献多少个子串？
- 偶数下标的总贡献是多少？
- 奇数下标的总贡献是多少？
提示
关键仍然是这句：
从下标 i 开始的子串个数 = n - i
只不过这次不是看元音辅音，而是看 i 的奇偶性。
