HackerRank Minion Game代码超时求助：长字符串用例无法通过

我为HackerRank的The Minion Game任务编写的代码，除超长字符串用例外，其余测试用例均已通过，但出现**Time limit exceeded（超时）**错误。我的代码如下：

from collections import defaultdict

def minion_game(string):
    vowels = {'A', 'E', 'I', 'O', 'U'}
    substrings = (string[i:j] for i in range(len(string)) for j in range(i+1, len(string)+1))
    counts = defaultdict(int)
    for s in substrings:
        counts[s] += 1
    kevinpoints = sum(counts[s] for s in counts if s[0] in vowels)
    Stuartpoints = sum(counts[s] for s in counts if s[0] not in vowels)
    if kevinpoints > Stuartpoints:
        print('Kevin ' + str(kevinpoints))
    elif kevinpoints < Stuartpoints:
        print('Stuart ' + str(Stuartpoints))
    else:
        print('Draw')

if __name__ == '__main__':
    s = input()
    minion_game(s)

问题根源 #

你的代码超时是因为生成并统计了所有子串的出现次数。对于长度为n的字符串，子串总数是n*(n+1)/2，属于O(n²)的时间复杂度。当字符串长度很大时，这种方法会消耗大量时间，直接触发超时。

而且题目计分规则根本不需要统计重复子串——只要是不同起始/结束位置的子串，不管内容是否重复，都算一次得分。你的统计重复次数的操作完全是多余的，反而拖慢了速度。

优化方案 #

直接遍历字符串的每个字符，根据其位置计算得分：

• 对于索引为i的元音字符，能贡献的得分是len(string) - i（从i开始，能生成到末尾的所有子串，共len(string)-i个）
• 对于索引为i的辅音字符，同理贡献len(string) - i的得分

优化后的代码：

def minion_game(string):
    vowels = {'A', 'E', 'I', 'O', 'U'}
    kevin_score = 0
    stuart_score = 0
    str_len = len(string)
    for idx, char in enumerate(string):
        if char in vowels:
            kevin_score += str_len - idx
        else:
            stuart_score += str_len - idx
    if kevin_score > stuart_score:
        print(f'Kevin {kevin_score}')
    elif stuart_score > kevin_score:
        print(f'Stuart {stuart_score}')
    else:
        print('Draw')

if __name__ == '__main__':
    s = input()
    minion_game(s)

优化效果 #

这个方法的时间复杂度是O(n)，只需要遍历字符串一次，无论输入字符串多长，都能在时间限制内完成计算，彻底解决超时问题。

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