# Repeated DNA Sequences

[https://leetcode.com/problems/repeated-dna-sequences/description/](https://leetcode.com/problems/repeated-dna-sequences/description/)

> All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
>
> Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
>
> For example,
>
> ```
> Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
>
> Return:
> ["AAAAACCCCC", "CCCCCAAAAA"].
> ```

## Thoughts

首先这个有歧义，开始一直以为是找No overlapping的重复子数组，看了别人的答案才知道不一定要no overlapping, 比如

If you enter your "AAAAAAAAAAA" as custom test and click "Run Code", you'll see that **expected** answer **is**

\["AAAAAAAAAA"].

知道了这点很容易想出naive 解法。即每次移动一位，把遇到的都记录下来。但这么做浪费空间。

还可以用整数存储方法。

> 这个思路非常简单，这里一共有四个字母：A，C，G，T。我们转换整数的思路如下：
>
> 1. A = 00，C = 01，G = 10，T = 11。
> 2. int key = 0, key = key << 2 | code(A|C|G|T)。
