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)
