Help in Maximum Permutation(Hackerrank University CodeSprint 4)

from collections import Counter

t = int(input())
while t:
    s1 = input()
    n = len(s1)
    s2 = input()
    m = len(s2)
    l = []
    d = {i: 0 for i in "qwertyuiopasdfghjklzxcvbnm"}
    td = {i: 0 for i in "qwertyuiopasdfghjklzxcvbnm"}

    for i in range(n):
        d[s1[i]] += 1
        td[s2[i]] += 1
    if td == d:

    for i in range(1, m - n):
        td[s2[i - 1]] -= 1
        td[s2[i + n - 1]] += 1

        if td == d:
            l.append(s2[i:i + n])
    l = Counter(l).most_common()
    if len(l) == 0:
        ans = l[0][0]
        c = l[0][1]
        for i in l:
            if i[1] > c:
                ans = i[0]
                c = i[1]
            elif i[1] == c:
                ans = min(ans, i[0])
    t -= 1

This is my code in python-3 for Maximum Permutation of Hackerrank University Codesprint 4

I’m getting runtime error for few cases. Could anyone please help me find what’s the mistake in above code which causes runtime error.

My approach

  • I’ve made a dictionary(d) which stores count of all characters in string s1 (smaller string)

  • I’ve also made a dictionary(td) which stores count of all characters in substring of s2[0, n) where n is length of s1

  • Now, if both the dictionaries are equal then I’ve pushed the substring in a list l

  • Repeating this for all other substrings I’ve increased and decreased the count of charcters I add and remove (in td) and if the dictionaries are equal then I’ve pushed the substring in a list l

  • Then the list of substrings is converted to list of tuples in which each tuple stores 2 values (string, frequency)

  • Then I find the most frequently occuring substring (lexicographically smallest if there are multiple substrings occuring same number of times)

Probably because u are trying to allocate too much memory(O(n^2)).

Consider the situation where both strings are equal.

Just out of curiousity,how much points did this fetch(because python can do anything)?

It fetches around 43 points :p. I used hashing in c++ that fetched same pts because of collisions. I think its time to switch completely to python . :stuck_out_tongue:

Yeah i too used hashing,suprisingly got 50 pts.

Yeah!! Memory is the problem. Thanks!!
It fetched me 30.11 points only.