Repeated DNA Sequences
Repeated DNA Sequences is a medium arrays & hashing problem solved with the sliding window · fixed pattern.
The best approach, optimal (2-bit rolling encoding), runs in O(n) time and O(2^20) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair of windows) up.
Problem
A DNA strand is written as a string s over the four letters 'A', 'C', 'G' and 'T'.
Return every sequence of exactly 10 consecutive letters that occurs at least twice in s (occurrences may overlap). List each such sequence once; the order of the list does not matter.
Examples
Example 1
- Input
s = "TTACGATCCATTACGATCCAGG"- Output
["TTACGATCCA"]- Why
- "TTACGATCCA" starts at index 0 and again at index 10; no other 10-letter window appears twice.
Example 2
- Input
s = "GGGGGGGGGGGG"- Output
["GGGGGGGGGG"]- Why
- The three windows of length 10 are identical. The sequence is reported once, not three times.
Example 3
- Input
s = "ACGT"- Output
[]- Why
- The string is shorter than 10, so there is no window at all.
Constraints
1 <= s.length <= 10^5s[i]is one of'A','C','G','T'.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare every pair of windows) | O(n² · 10) | O(n) |
| Better (hash set of windows) | O(10 · n) | O(10 · n) |
| Optimal (2-bit rolling encoding) | O(n) | O(2^20) |
1Brute force (compare every pair of windows)
O(n² · 10)Up to n²/2 window pairs, each compared in up to 10 steps.O(n)The answer list (and its lookup set) can hold O(n) windows.For each window, check whether the same 10 letters appear at any later start. Add it to the answer the first time a match is found, skipping windows already in the answer.
- For i in 0..n-10, let w = s[i..i+9]; skip it if w is already in the answer.
- For j in i+1..n-10, if s[j..j+9] equals w, add w to the answer and stop.
- Return the answer.
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int n = s.length();
Set<String> found = new LinkedHashSet<>();
for (int i = 0; i + 10 <= n; i++) {
String w = s.substring(i, i + 10);
if (found.contains(w)) continue;
for (int j = i + 1; j + 10 <= n; j++) {
if (s.regionMatches(j, w, 0, 10)) {
found.add(w);
break;
}
}
}
return new ArrayList<>(found);
}
}class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
n = len(s)
found = []
found_set = set()
for i in range(n - 9):
w = s[i:i + 10]
if w in found_set:
continue
for j in range(i + 1, n - 9):
if s.startswith(w, j):
found.append(w)
found_set.add(w)
break
return foundclass Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.size();
vector<string> found;
unordered_set<string> foundSet;
for (int i = 0; i + 10 <= n; i++) {
string w = s.substr(i, 10);
if (foundSet.count(w)) continue;
for (int j = i + 1; j + 10 <= n; j++) {
if (s.compare(j, 10, w) == 0) {
found.push_back(w);
foundSet.insert(w);
break;
}
}
}
return found;
}
};function findRepeatedDnaSequences(s) {
const n = s.length;
const found = new Set();
for (let i = 0; i + 10 <= n; i++) {
const w = s.substring(i, i + 10);
if (found.has(w)) continue;
for (let j = i + 1; j + 10 <= n; j++) {
if (s.startsWith(w, j)) {
found.add(w);
break;
}
}
}
return [...found];
}2Better (hash set of windows)
O(10 · n)Each of the n - 9 windows is copied and hashed in 10 steps.O(10 · n)The sets store up to n windows of 10 characters each.Slide over all windows once. Keep a set of windows seen so far; when a window is already in it, it is a repeat. A second set makes sure each repeat is reported only once.
- seen = {}, repeated = {}.
- For each i, w = s[i..i+9]: if w is in seen, add it to repeated, else add it to seen.
- Return the contents of repeated.
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> seen = new HashSet<>(), repeated = new HashSet<>();
for (int i = 0; i + 10 <= s.length(); i++) {
String w = s.substring(i, i + 10);
if (!seen.add(w)) repeated.add(w);
}
return new ArrayList<>(repeated);
}
}class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
seen, repeated = set(), set()
for i in range(len(s) - 9):
w = s[i:i + 10]
if w in seen:
repeated.add(w)
else:
seen.add(w)
return list(repeated)class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_set<string> seen, repeated;
for (int i = 0; i + 10 <= (int)s.size(); i++) {
string w = s.substr(i, 10);
if (!seen.insert(w).second) repeated.insert(w);
}
return vector<string>(repeated.begin(), repeated.end());
}
};function findRepeatedDnaSequences(s) {
const seen = new Set(), repeated = new Set();
for (let i = 0; i + 10 <= s.length; i++) {
const w = s.substring(i, i + 10);
if (seen.has(w)) repeated.add(w);
else seen.add(w);
}
return [...repeated];
}3Optimal (2-bit rolling encoding)
O(n)Each character costs a shift, an OR and a mask; strings are only built for reported windows.O(2^20)A fixed table with one counter per possible 20-bit code (about a million entries).Map A, C, G, T to 0..3. A window of 10 letters is then a 20-bit number. Moving the window right is code = ((code << 2) | next) & (2^20 - 1), which is O(1). Count windows in an array of size 2^20 and output a window exactly when its count goes from 1 to 2.
- If n < 10, return an empty list.
- Keep code = 0 and count = new byte/int array of size 2^20.
- For each i, shift in the 2 bits of s[i] and mask to 20 bits.
- Once i >= 9, increment count[code]; if it just became 2, add s[i-9..i] to the answer.
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<>();
int n = s.length();
if (n < 10) return res;
int[] val = new int[128];
val['C'] = 1;
val['G'] = 2;
val['T'] = 3;
byte[] count = new byte[1 << 20];
int mask = (1 << 20) - 1, code = 0;
for (int i = 0; i < n; i++) {
code = ((code << 2) | val[s.charAt(i)]) & mask;
if (i >= 9 && count[code] < 2 && ++count[code] == 2) {
res.add(s.substring(i - 9, i + 1));
}
}
return res;
}
}class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
n = len(s)
if n < 10:
return []
val = {"A": 0, "C": 1, "G": 2, "T": 3}
count = bytearray(1 << 20)
mask = (1 << 20) - 1
code = 0
res = []
for i, ch in enumerate(s):
code = ((code << 2) | val[ch]) & mask
if i >= 9 and count[code] < 2:
count[code] += 1
if count[code] == 2:
res.append(s[i - 9:i + 1])
return resclass Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
int n = s.size();
if (n < 10) return res;
int val[128] = {0};
val['C'] = 1;
val['G'] = 2;
val['T'] = 3;
vector<unsigned char> count(1 << 20, 0);
int mask = (1 << 20) - 1, code = 0;
for (int i = 0; i < n; i++) {
code = ((code << 2) | val[(int)s[i]]) & mask;
if (i >= 9 && count[code] < 2 && ++count[code] == 2) {
res.push_back(s.substr(i - 9, 10));
}
}
return res;
}
};function findRepeatedDnaSequences(s) {
const n = s.length;
if (n < 10) return [];
const val = { A: 0, C: 1, G: 2, T: 3 };
const count = new Uint8Array(1 << 20);
const mask = (1 << 20) - 1;
let code = 0;
const res = [];
for (let i = 0; i < n; i++) {
code = ((code << 2) | val[s[i]]) & mask;
if (i >= 9 && count[code] < 2 && ++count[code] === 2) {
res.push(s.substring(i - 9, i + 1));
}
}
return res;
}Edge cases to test
- Strings shorter than 10 characters
- Overlapping occurrences, like a run of one repeated letter
- A sequence that appears three or more times must still be listed only once
- Exactly 10 characters: one window, which cannot repeat
Hints
Hint 1
There are only n - 9 windows of length 10. Can you remember which ones you have already seen?
Hint 2
A set of seen windows plus a set of already-reported windows gives an O(10 · n) solution.
Hint 3
With 4 letters, each character fits in 2 bits, so a window fits in 20 bits. Slide the window by shifting in 2 bits and masking, and index plain arrays of size 2^20 instead of hashing strings.
FAQ
What is the best time complexity for Repeated DNA Sequences?
Optimal (2-bit rolling encoding) runs in O(n) time and O(2^20) extra space. Each character costs a shift, an OR and a mask; strings are only built for reported windows.
Which pattern does Repeated DNA Sequences use?
It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.
Is there a brute force solution for Repeated DNA Sequences?
Yes. Brute force (compare every pair of windows) takes O(n² · 10) time and O(n) space. For each window, check whether the same 10 letters appear at any later start.
Which edge cases should I test for Repeated DNA Sequences?
Strings shorter than 10 characters; Overlapping occurrences, like a run of one repeated letter; A sequence that appears three or more times must still be listed only once; Exactly 10 characters: one window, which cannot repeat.