Repeated DNA Sequences

Problem: Repeated DNA Sequences

To solve this problem, we can maintain a dictionary which stores all sub-string with length of 10. If we found one occurs more than once, we can append it to our answer.

Code in Python:

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        dict, ans = {}, []
        for i in xrange(10, len(s)+1):
            string = s[i-10:i]
            if string not in dict:
                dict[string] = 1
            elif dict[string] == 1:
                ans.append(string)
                dict[string] = 2
        return ans

As a problem tagged as "Bit Manipulation", there's another solution, which use bit manipulation to turn letters into integers, thus reduce the space.