"Mixing Proteins" HackerRank challenge 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['fromLetter+toLetter']='mutatedLetter'
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&lt;n:
        #handle the protein wrap-around
        if pos == n-1:
            mutated += matrix[proteins[-1]+proteins[0]]
        else:
            mutated+= matrix[proteins[pos:pos+2]]

        pos+=1
    proteins = mutated
print(proteins)
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.