HackerRank: The Minion Game Notes

Background

This article was written down when I was doing a Python challenge on HackerRank: The Minion Game.

Hints

If you haven't passed this question and want to have some hints. There are two hints I think might be helpful:

• The solution can be done with one loop by using simple math.
• Try to write down all substrings starting with each letter in S and see whether you can find some patterns.

Problem

The problem gives you a string S and says that two players Stuart and Kevin will make substrings using the letters of S. S will contain only uppercase letters: [A-Z] and \( 0 < len(S) < 10^{6}\)

• Kevin has to make words starting with vowels ("AEIOU").
• Stuart has to make words starting with consonants (letters other than "AEIOU")

A player will get +1 point for each occurrence of the substring in the string S.

For example, "AN" appears twice in "BANANA", so it is counted as 2 points.

In short, we need to separate all substrings into two categories: starting with vowels or starting with consonants and then count the total occurrence of substrings in each category.

Output:

We need to output the "winner score" or "Draw" if no winner.

Stuart 12

Analysis

Initial Thought

At first, I tried to list all combinations of the substrings and count the scores respectively:

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))

This is the Wrong way since it gets "Time Limit Exceeded" easily.

Then I saw this hint from the Discussion section:

All Substrings

We can then try to list all the substrings by using each letter in S.

There is an important point to remember here. These 6 columns are independent. What I mean by independent is that there is no double-counting for the same substring in the same position.

For example, the "ANA" appears twice here, but they are in different positions. It is not an identical "ANA" string being counted twice in two categories.

This is an easy concept, but if you ignore it or if you feel even a little bit confused here, you won't be able to come up with the next step.

How to calculate the total number of substrings?

The next thing we observe here is how to calculate the total number of substrings for a given string.

Let's take a look at the letter "B" here. The substrings using it as the first letter are "B", "BA", "BAN"...., "BANANA". It is basically starting with the letter itself and expanding the substring until the end.

Therefore, the number of substrings caused by this letter is the length of this letter until the end of the string.

So the total number of substrings will be the sum of the number of substrings caused by each letter. Thus in the last row of the table above, \(6+5+4+3+2+1 = 21\) is the total number of substrings of "BANANA". It means that for a string with length n, the number of substrings will be \(= 1 + 2 + 3+ ...+n = \frac{n(n+1)}{2}\).

As we can see, the \(21\) is the sum of 12 and 9 which are the scores of Stuart and Kevin respectively.

We should also be aware that this method is calculating the number of substrings instead of the number of distinct substrings, so it will count the repeated substrings. But that is what want for this question.

The Simple Solution

Let's go back to our problem. How can we calculate the score of Kevin's when S="BANANA"? We just simply add the number of substrings for the column "A"s, which is \(5+3+1=9\).

That is basically our solution to this problem. We iterate the string once, for each character, we check whether it is a vowel or a consonant, and then add the length of it until the end of S to the corresponding score.

Solution

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))

Some Algorithm Books That I Am Using

(This part will contain affiliate links. Purchases made from these links will give me some money. It doesn't cost you extra. Thank you.)

1. Grokking Algorithms (by Aditya Bhargava)

Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People

Get it now:

2. Introduction to Algorithms, fourth edition (by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)

Introduction to Algorithms, fourth edition

Get it now:

3. Competitive Programming 4 - Book 1: The Lower Bound of Programming Contests in the 2020s (Steven Halim, Felix Halim, Suhendry Effendy) (I have the third version, but I believe the fourth will be better.)

Competitive Programming 4 - Book 1

Get it now:

Book 1

If you only want to buy one, I believe the first one will be a good book for introduction to algorithms, while the second is the best reference book if you want to have some solid theoretical background. The third one should only be bought if you really want to join in competitive programming.