181. Repeated Gene Snippets
A lab stores a DNA strand as a string dna made only of the letters A, C, G and T. Researchers are hunting for short motifs that show up more than once. A motif here is any block of exactly ten consecutive letters, and two blocks count as occurrences of the same motif when they spell the same ten letters, even if they overlap in the strand.
Return every ten-letter motif that occurs at least twice in dna. Each motif must be listed exactly once, and the motifs may be returned in any order. If the strand has fewer than ten letters, or no motif repeats, return an empty array.
Example 1
- Input:
- dna = "AAAAAAAAAAAA"
- Output:
- ["AAAAAAAAAA"]
- Explanation:
The twelve letters contain three windows of ten letters and all of them read
AAAAAAAAAA, so that single motif is reported once.
Example 2
- Input:
- dna = "ACGTACGTAC"
- Output:
- []
- Explanation:
The strand has exactly ten letters, so there is only one window and nothing can repeat.
Example 3
- Input:
- dna = "GATTACAGATTACAGATTACAG"
- Output:
- ["ACAGATTACA","ATTACAGATT","CAGATTACAG","GATTACAGAT","TACAGATTAC","TTACAGATTA"]
- Explanation:
The strand repeats with period 7, so each window starting at positions 0 through 5 shows up again 7 letters later, which gives six motifs. Windows starting at position 6 or later occur only once.
Constraints
1 ≤ dna.length ≤ 20000
dna[i] is one of 'A', 'C', 'G', 'T'
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)