I am doing this problem on HackerRank and I'm failing test cases because it's taking too long to run when n and k get over 8000. I believe the dictionary lookup should be \$O(1)\$ while lists are \$O(n)\$. Would it be faster to store the DNA string in another dictionary where the array position is the key? I'm not sure of any other optimizations I can make.

Essentially, given a string of n characters, iterate through that string k times while swapping values according to dictionary key/value pairs. So a string 'AAC' would look at 'AA'->'A', 'AC'->'C', and because of wrap-around, 'CA'->'C'. So after one iteration, 'AAC' becomes 'ACC'. Now repeat k times.

inp = input().split(' ')
n, k = inp[0], inp[1]
proteins = input()
#generated the dictionary with other python scripts since it's unchanging
#see challenge on Hackerrank for original table
matrix = {'AA': 'A', 'BD': 'C', 'AC': 'C', 'AB': 'B', 'AD': 'D', 'BB': 'A', 'BC': 'D', 'CC': 'A', 'CB': 'D', 'CA': 'C', 'DB': 'C', 'DC': 'B', 'CD': 'B', 'DA': 'D', 'DD': 'A', 'BA': 'B'}

for i in range(k):
    pos = 0
    mutated = ''
    while pos<n:
        #handle the protein wrap-around
        if pos == n-1:
            mutated += matrix[proteins[-1]+proteins[0]]
            mutated+= matrix[proteins[pos:pos+2]]

    proteins = mutated

1 Answer 1


I encourage you to abandon your present approach.

Instead, try expressing each of your A/B/C/D proteins as integer numbers. Then express those integer numbers in binary form, and see if you can determine the operation(s) underlying the very, very regular pattern visible in the table given in the problem.

If you transcode the "protein sequences" to a series of 2-bit numbers, I believe you can profitably perform your mutations at a high rate of speed.

  • \$\begingroup\$ Have you found a working solution for large enough n and k? Obvious solutions on this vain are being too slow for me \$\endgroup\$ Oct 9, 2017 at 4:16
  • \$\begingroup\$ @OscarSmith I had to take Austin's advice to get it to work for large values of n/k. I have to admit, the level of refinement required for the full solution caught me off guard, but I guess that's why it's a 'hard' question. :) \$\endgroup\$ Oct 9, 2017 at 12:55
  • \$\begingroup\$ @UnclosedParenthesis Can you do k%n rounds instead of k? \$\endgroup\$
    – JollyJoker
    Oct 9, 2017 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.