Repeated DNA Sequences
Repeated DNA Sequences: find every 10-letter DNA substring that occurs more than once, each reported exactly once.
- 1 <= s.length <= 10⁵
- s[i] is either 'A', 'C', 'G', or 'T'.
Intuition
Repeated dna sequences finds every 10-letter substring appearing more than once in a DNA string. The alphabet is just A, C, G, T, and the window length is fixed at 10.
The direct approach slides a 10-character window and counts occurrences in a hash map. Each substring costs O(10) to extract and hash, so the total is O(10n) — which is O(n) with a constant of 10, and entirely acceptable.
The subtlety is in what to return:
- Each repeated sequence appears once in the output regardless of how many times it occurs, so a set is needed for results, not a list.
Adding to the result the moment a count reaches 2 — rather than every time it is seen — is the cleaner way to enforce that. A sequence appearing five times would otherwise be added four times.
The optimisation the problem invites uses the four-letter alphabet. Each base fits in 2 bits, so a 10-letter window fits in 20 bits — comfortably inside a 32-bit integer:
A rolling hash then updates in O(1) per position: shift left 2, mask to 20 bits, and OR in the new base. That removes the per-window substring extraction, making the scan genuinely O(n).
The mask matters. Without & 0xFFFFF the value keeps growing and old bases are never dropped, so windows stop being 10 characters long.
Strings shorter than 10 characters have no valid window, so the answer is empty — worth checking before the loop.
Both versions use O(n) space for the maps and result.
A fixed 10-character window over a 4-letter alphabet. Two sets are needed, not one: seen records every window, added prevents a sequence appearing three or more times from being reported repeatedly.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n) time and O(n) space.
Slide a fixed window
Only 10-character substrings matter, so the window never changes size. Extract each and count occurrences in a hash map.
Handle short inputs
Strings under 10 characters have no valid window, so return empty before the loop rather than indexing out of range.
Add at exactly two
Append to the result when a count reaches 2, not on every sighting. A sequence appearing five times would otherwise be added four times.
Encode bases in two bits
With only four letters, each base fits in 2 bits and a 10-letter window in 20 — comfortably inside a 32-bit integer.
Roll the hash in O(1)
Shift left 2, mask to 20 bits, and OR in the new base. This removes the per-window substring extraction, making the scan genuinely linear.
Apply the mask
Without & 0xFFFFF the value keeps growing and old bases are never dropped, so the window silently stops being 10 characters.
Cost of the approach
Both versions are O(n) time — the rolling hash with a smaller constant — and O(n) space for the counts and result.
Solution & live demo
Common pitfalls
Using one set and reporting on every repeat
if window in seen:
result.append(window)
seen.add(window)if window in seen and window not in added:
added.add(window)
result.append(window)A sequence occurring four times would be appended three times. The output must list each repeated sequence once, which requires tracking what has already been reported.
Getting the loop bound wrong
for i in range(len(s) - 10):
for i in range(len(s) - 9):
The last valid window starts at len(s) - 10, so the range must run to len(s) - 9 exclusive. Stopping one early silently drops the final window — which may be the only repeat.
Returning the added set directly
return list(added)
return result
Set iteration order is unspecified, so the output ordering varies between runs. Appending to a list as matches are found gives a deterministic order — and some judges compare order-sensitively.
Edge cases
the loop range is empty, so the result is []
added-set stops it from being appended more than once
seen-set fills up but added stays empty, returning []
each window is still evaluated independently by its own 10-character slice