187.-repeated-dna-sequences.md

187. Repeated DNA Sequences

• Medium

• The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

  • For example, "ACGAATTCCG" is a DNA sequence.

  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.

Analysis

The idea for this problem is to use a dictionary to record the occurance of each sequence and if it appears twice then add it to the answer.

The idea of sliding window comes when I see that there is a fixed sized window, but it doesn't do much then simply slicing the string.

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        answer=[]
        n=len(s)
        if n<10:
            return answer
        
        curr=s[:10]
        seen=collections.defaultdict(int)
        seen[curr]=1
        for i in range(10,n):
            curr=curr[1:]+s[i]
            seen[curr]+=1
            if seen[curr]==2:
                answer.append(curr)
        return answer