You are not logged in. Please login at www.codechef.com to post your questions!

×

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)

asked 26 Feb '18, 00:51

a_d_i's gravatar image

2★a_d_i
1746
accept rate: 23%


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)?

link

answered 26 Feb '18, 08:23

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
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) soham12346★

Yeah i too used hashing,suprisingly got 50 pts.

(26 Feb '18, 12:23) vivek_19982996★

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

(26 Feb '18, 22:29) a_d_i2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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