class Solution:
# @param s, a string
# @return a list of strings
def findRepeatedDnaSequences(self, s):
repeatSeq = set()
addedSeq = set()
result = []
answer = []
charToBin = {'A' : 0b00, 'T' : 0b01, 'G' : 0b10, 'C' : 0b11}
mask = 0xfffff
current = 0
for i in range(len(s)):
#create bit
x = charToBin[s[i]]
current = x
if i >= 9:
if current in repeatSeq:
if current not in addedSeq:
addedSeq.add(current)
result.append(i  9)
else:
repeatSeq.add(current)
#shift
current <<= 2
#mask
current &= mask
for i in result:
answer.append(s[i : i + 10])
return answer
Rolling hash AC Python solution.


Same idea, but shorter solution
class Solution(object): def findRepeatedDnaSequences(self, s): repeat, add = set(), set() charToBin = {'A':0b00, 'T':0b01, 'G': 0b10, 'C':0b11} mask = 0xfffff cur = 0 for i in range(len(s)): x = charToBin[s[i]] cur = x if i >= 9: if cur not in add: add.add(cur) else: repeat.add(s[i9:i+1]) cur <<= 2 cur &= mask return list(repeat)
