Repeated DNA Sequences — Solution in Python, Java & C++
Repeated DNA Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Repeated DNA Sequences is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and LinkedIn interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window, Rolling Hash
- Asked at: Amazon, Google, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A DNA strand is written as a string over the letters A, C, G and T.
Given a strand s, return every substring of length exactly 10 that occurs more than once in s (occurrences may overlap). Each such substring is listed once, and the list is sorted in ascending lexicographic order. Return an empty list if there is none.
Example 1
Input: s = "ACGTTGCAACACGTTGCAACGT"
Output: ["ACGTTGCAAC"]
Explanation: `ACGTTGCAAC` starts at indices 0 and 10.
Example 2
Input: s = "CCCCCCCCCCCC"
Output: ["CCCCCCCCCC"]
Explanation: Overlapping occurrences at 0, 1 and 2 count.
Example 3
Input: s = "GATTACA"
Output: []
Constraints
1 <= s.length <= 10^5s[i] is one of 'A', 'C', 'G', 'T'
Hints for Repeated DNA Sequences
Hint 1
Slide a window of length 10 across
sand count each window you see.Hint 2
A hash map from window to count finds the repeats in one pass; report a window the moment its count reaches 2 so it is listed once.
Hint 3
With four letters a window fits in 20 bits (2 bits per letter), so it can be kept as an integer and updated in O(1) per step.
How to solve Repeated DNA Sequences
Every candidate is one of the n − 9 windows of length 10, so counting windows in a hash map finds exactly the repeated ones.
Approach
- For each start
ifrom 0 ton − 10, take the windows[i..i+9]. - Increment its count; when the count becomes exactly 2, append the window to the answer.
- Sort the answer.
- (Optional) Encode A, C, G, T as 0–3 and keep the window as a 20-bit integer: shift left by 2, add the new letter, mask to 20 bits. Because A < C < G < T, sorting the codes numerically sorts the strings too.
Why it works
A length-10 substring that occurs twice is, by definition, two windows with equal content, so it reaches count 2 in the map; adding it only at that moment lists each repeated sequence exactly once no matter how many more times it appears.
Complexity
- Time —
O(n · 10) with string keys, O(n) with the rolling 20-bit code (plus sorting the answer) - Space —
O(n)
Pitfalls
- Adding a window every time its count is ≥ 2 lists sequences that occur three times twice.
- Strings shorter than 10 have no windows — make sure the loop bound does not go negative.
- Occurrences may overlap (
CCCCCCCCCCCrepeatsCCCCCCCCCC); do not skip ahead after a match.
Reference solution
Python
from typing import List
def findRepeatedDnaSequences(s: str) -> List[str]:
seen = {}
res = []
for i in range(len(s) - 9):
t = s[i:i + 10]
c = seen.get(t, 0) + 1
seen[t] = c
if c == 2:
res.append(t)
res.sort()
return resJava
public static String[] findRepeatedDnaSequences(String s) {
Map<String, Integer> seen = new HashMap<>();
List<String> res = new ArrayList<>();
for (int i = 0; i + 10 <= s.length(); i++) {
String t = s.substring(i, i + 10);
int c = seen.getOrDefault(t, 0) + 1;
seen.put(t, c);
if (c == 2) res.add(t);
}
Collections.sort(res);
return res.toArray(new String[0]);
}C++
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<string, int> seen;
vector<string> res;
for (int i = 0; i + 10 <= (int)s.size(); i++) {
string t = s.substr(i, 10);
if (++seen[t] == 2) res.push_back(t);
}
sort(res.begin(), res.end());
return res;
}JavaScript
var findRepeatedDnaSequences = function(s) {
var seen = new Map();
var res = [];
for (var i = 0; i + 10 <= s.length; i++) {
var t = s.substring(i, i + 10);
var c = (seen.has(t) ? seen.get(t) : 0) + 1;
seen.set(t, c);
if (c === 2) res.push(t);
}
res.sort();
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets