HackerRank minion游戏Python嵌套循环代码运行超时优化求助

• 原代码时间复杂度过高，最坏情况达到O(n³)：第一层遍历起始索引，第二层遍历结束索引生成子串（已达O(n²)量级），后续还遍历整个字符串统计当前子串的出现次数，额外多了O(n)的开销，当输入字符串长度达到数千级别时，必然触发超时。
• 逻辑冗余：引入集合做子串去重、全局统计子串出现次数的操作完全不必要，没有抓住题目得分规则的本质。

得分规则的底层逻辑可简化为：每个以元音开头的子串，无论内容是什么、是否和其他子串重复，只要存在就给Kevin加1分；同理辅音开头的子串给Stuart加1分。
对于索引为i的字符，以它为开头的子串总共有len(string) - i个，因此只需要遍历一次字符串，判断每个位置的字符属性，直接把对应子串数量加到对应玩家的分数中即可，时间复杂度直接降到O(n)。

def minion_game(string):
    vowels = {'A', 'E', 'I', 'O', 'U'}
    str_len = len(string)
    stuart, kevin = 0, 0
    for i in range(str_len):
        if string[i] in vowels:
            kevin += str_len - i
        else:
            stuart += str_len - i
    if stuart > kevin:
        print('Stuart', stuart)
    elif kevin > stuart:
        print('Kevin', kevin)
    else:
        print('Draw')

以官方样例输入BANANA（长度为6）为例：

• 索引0为B（辅音），加6 → stuart=6
• 索引1为A（元音），加5 → kevin=5
• 索引2为N（辅音），加4 → stuart=10
• 索引3为A（元音），加3 → kevin=8
• 索引4为N（辅音），加2 → stuart=12
• 索引5为A（元音），加1 → kevin=9
  最终输出Stuart 12，和官方样例结果完全匹配。

内容的提问来源于stack exchange，提问作者Apurva Gaurav