HackerRank: The Minion Game 笔记和题解

背景

这篇笔记是在我做 HackerRank 上的一道 Python 题目时写下的。题目叫做 The Minion Game。这道题在 HackerRank 上是 Medium 难度，我一开始交的一个答案 TLE（Time Limit Exceeded）了，想了好一会才想到了 O(N) 的答案。

提示

如果你还没通过这道题，想要有点提示的话，可以试试我这两个提示：

• 答案是可以用一个 loop 和简单的数学做出来的
• 试着将以每个字母为开头的 substring 写出来，找一下规律。

问题

问题给了你一个 string S，告诉你说 Stuart 和 Kevin 在玩游戏，他们需要从 $S$ 里面做 substring。$S$ 只包含了大写字母 [A-Z]，以及 $0 < len(S) < 10^{6}$。

• Kevin 必须组 Vowels (元音字母) 开头的 substrings ("AEIOU")
• Stuart 必须组 Consonants (辅音字母) 开头的 substrings (非 "AEIOU" 的字母)

每人组的 substrings 在 $S$ 里出现的次数对应了他们的分数。输出胜者的名字加分数，例如"Stuart 12"。如果平手就输出 "Draw"。

这是官方给的例子，S = "BANANA"。

可以看到这里，"AN" 在 "BANANA" 里出现了两次，所以它的分数是2。

总结：就是将 $S$ 的 substrings 分为两类（元音开头和非元音开头），统计每类的总出现次数。

分析

一开始的想法

我一开始的解法是将所有 substrings 用 combiantion 打出来，然后一个个统计分数：

from itertools import combinations
def minion_game(string):
    vowels = "AEIOU"
    
    Kevin, Stuart = 0, 0
    for i, j in combinations(range(len(string) + 1), r = 2):
        if string[i:j][0] in vowels:
        	Kevin+=1
        else:
        	Stuart+=1
            
    if Stuart > Kevin:
    	print("Stuart {}".format(Stuart))
    elif Stuart == Kevin:
    	print("Draw")
    else:
    	print("Kevin {}".format(Kevin))

但这个方法就很容易 TLE。

然后我在 Discussion 看到了这条提示：

这条评论说不需要用 nested loops，在 string 上做一次循环就可以了，说要思考如何用数学去解答。

所有的 Substrings (子串)

我们就可以试着把"BANANA" 的每个字母开头的 substring 列出来看看，类似这样：

这里需要注意一个容易混淆的点，就是这 6 列是完全独立的，不存在同一个位置的 substring 被重复计算。

比如上表出现的两个 "ANA"，他们是在两个不同的位置。并不会出现一个位置的 "ANA" 被前后重复计算的情况。

这是个蛮简单的点，但是忽略了可能会导致你想不出下一步。

如何计算一个 string (字符串) 的 substrings (子串) 数量

接下来我们观察到，其实对于每个位置的字母来说，以它为首的 substring 数量，就是它到末尾的长度。比如这里的 "B"，由 "B" 自己开始，就是 substrings 不断延伸一个单位直到末尾 (B, BA, BAN..., BANANA)。因此由 "B" 产生的 substring 数量就是 "B" 到末尾的长度。

所以这里的 $6+5+4+3+2+1=216+5+4+3+2+1=21$ 就是 "BANANA" 的总 substrings 数量。也就是对于一个长度为 n 的 string 来说，它的 substrings 总数 $ = 1 + 2 + 3+ ...+n = \frac{n(n+1)}{2}$。
而这里的 $21$ 其实就是上面的 $12$ 分加 $9$ 分。

需要注意的是，这种算法是算上了重复的 substrings，是 number of substrings 而不是 number of distinct substrings，但这正是我们在这题里想要的。

最终解法

那么回到题目，Kevin 的 $9$ 分是怎么算出来的呢？我们只需要把三个 "A" 的三列的数字加起来就行了，就是 $5+3+1=95+3+1=9$。

所以这基本就是我们对这道题的解法，遍历整个 S 一次，每个字母先分辨它是否是元音，然后将它到末尾的长度加到对应的 score 上就可以了。

题解

def minion_game(string):
    vowels = "AEIOU"
    l = len(string)
    Kevin, Stuart = 0, 0
    
    for i in range(l):
        if string[i] in vowels:
        	Kevin += l-i
        else:
        	Stuart += l-i
            
    if Stuart > Kevin:
    	print("Stuart {}".format(Stuart))
    elif Stuart == Kevin:
    	print("Draw")
    else:
    	print("Kevin {}".format(Kevin))