CODEWITHSUNDEEP
django
user12697535
user12697535

Reputation:

Related to string and substring

What is the efficient way to calculate total number of unique substrings in a string

Upvotes: 0

Views: 1053

Answers (1)

Anatolii
Anatolii

Reputation: 14660

Introduction

If we take a look at your double loop below:

for i in range(l):
    for j in range(1,l-i+1):
        mylist.append(string[i:j+i])

then it becomes clear why your solution terminates with Runtime Error for some test cases - the space complexity in the loop is way too high! The number of elements in mylist is proportional to n2, where n is a length of the original string. As per task description, the string length can approach 10^6 characters, your mylist size can turn 10^12 respectively.

To make matters worse, elements of mylist are not just single characters but substrings of the original string. So, the space complexity is actually O(n3). Since your sample input string is of length 5000, you get way over 512MB that is the maximum allowed threshold as described here.

How to improve space complexity

You must realise that you don't need any mylist to count scores of Stuart and Kevin. Instead, you could just count their scores right in your loop. Why? Because it already generates all substrings of the original string, in which string[i] is the first character of the given substring. Then, if it's a vowel, you increment Kevin's score, otherwise - that of Stuart:

stuart=0
kevin=0  
for i in range(l):
    for j in range(1,l-i+1):
        if string[i] in vowel:
            kevin += 1
        else:
            stuart += 1

How to improve time complexity

In the previous paragraph, we made a significant improvement because Runtime Error is gone, but the solution will still time out for some test cases because its time complexity is still too high - O(n2).

To improve it, you must realise that the number of substrings starting with string[i] is len(string) - i. Hence, there's no need for the inner loop and the original double loop can be simplified to a O(n) time complexity solution:

stuart = 0
kevin = 0  
for i in range(l):
    if string[i] in vowel:
        kevin += (l - i)
    else:
        stuart += (l - i)

Full Code

def minion_game(string):
    l = len(string)
    vowel=['A','E','I','O','U']

    stuart = 0
    kevin = 0  
    for i in range(l):
        if string[i] in vowel:
            kevin += (l - i)
        else:
            stuart += (l - i)

    if kevin > stuart:
        print(f'Kevin {kevin:d}')
    elif stuart > kevin:
        print(f'Stuart {stuart:d}')
    else:
        print('Draw')

Upvotes: 2

Related Questions