# 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:
l.append(s2[:n])

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:
print(-1)
else:
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])
print(ans)
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 .

Yeah i too used hashing,suprisingly got 50 pts.

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