CODEWITHSUNDEEP
pythonpython-3.x
Srinabh
Srinabh

Reputation: 400

Timeout on long test case, sub string game

The problem statement is as given below

Game Rules

Both players are given the same string, . Both players have to make substrings using the letters of the string . Stuart has to make words starting with consonants. Kevin has to make words starting with vowels. The game ends when both players have made all possible substrings.

Scoring A player gets +1 point for each occurrence of the substring in the string .

For Example: String = BANANA Kevin's vowel beginning word = ANA Here, ANA occurs twice in BANANA. Hence, Kevin will get 2 Points. Your task is to determine the winner of the game and their score.

Code:

def minion_game(string):
    kevin,stuart=0,0
    for i in range(0,len(string)):
        for j in range(i,len(string)):
            if string[i:j+1][0]=='A' or string[i:j+1][0]=='E' or string[i:j+1][0]=='I' or string[i:j+1][0]=='O' or string[i:j+1][0]=='U':
                kevin=kevin+1
            else:
                stuart=stuart+1
    if kevin>stuart:
        print('Kevin',kevin)
    elif kevin<stuart:
        print('Stuart',stuart) 
    else:
        print('Draw')



s = input()
minion_game(s)

Input: Click here

Expected output: Stuart 7501500

Output: Terminated due to timeout

Upvotes: 1

Views: 2232

Answers (2)

RISHABH CHATURVEDI
RISHABH CHATURVEDI

Reputation: 1

def minion_game(string):

c=0
c1=0
v=('A','E','I','O','U')
for i in range(0,len(string)):
    sa=""
    if string[i] not in v:
        sa=sa+string[i]
        c=c+1
        for j in range(i,len(string)-1):
            sa=sa+string[i+1]
            c=c+1
            i=i+1
    else:
        sa=sa+string[i]
        c1=c1+1
        for j in range(i,len(string)-1):
            sa=sa+string[i+1]
            c1=c1+1
            i=i+1
if(c>c1):
    print('Stuart '+str(c))
elif(c1>c):
    print('Kevin '+str(c1))
elif(c1==c):
    print('Draw')

Upvotes: 0

Mitch
Mitch

Reputation: 3416

Here was my old solution to the problem 

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

    if kevin == stuart:
        print("Draw")
    elif kevin > stuart:
        print("Kevin " + str(kevin))
    else:
        print("Stuart " + str(stuart))

The trick is to realize you don't need to try every combination. Once you see the vowel or consonant you can be sure that there is the length of the current string sub strings left, so you can just add that many points

So for example, given the word Banana, we see a B and we immediately know that {B, BA, BAN, BANA, BANAN, BANANA} are all going to give points to Stuart. No need to keep checking

Upvotes: 3

Related Questions