# 187. Repeated DNA Sequences
from collections import defaultdict

"""
the dna sequence is composed of a series of nucleotides abbreviated as A, C,
G, and T. when studying dna it is useful to identify repeated sequences
within the dna. given a string 's' that represents a dna sequence, return all
the 10 letter long sequences (substrings) that occur more than once in a dna
molecule. you may return the answer in any order
"""


class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        seq = defaultdict(int)
        for i in range(len(s)):
            seq[s[i : i + 10]] += 1
        return [key for key, val in seq.iteritems() if val > 1]


if __name__ == "__main__":
    obj = Solution()
    print(obj.findRepeatedDnaSequences(s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"))
    print(obj.findRepeatedDnaSequences(s="AAAAAAAAAAAAA"))