×

Help in Maximum Permutation(Hackerrank University CodeSprint 4)

 0 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) asked 26 Feb '18, 00:51 2★a_d_i 174●6 accept rate: 23%

 0 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)? answered 26 Feb '18, 08:23 1.6k●2●9 accept rate: 23% 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 . :p (26 Feb '18, 11:56) Yeah i too used hashing,suprisingly got 50 pts. (26 Feb '18, 12:23) Yeah!! Memory is the problem. Thanks!! It fetched me 30.11 points only. (26 Feb '18, 22:29) a_d_i2★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×545
×528
×354
×310
×280
×49
×8

question asked: 26 Feb '18, 00:51

question was seen: 328 times

last updated: 26 Feb '18, 22:29