187. Repeated DNA Sequences

187

MediumTrie and Advanced String SearchSliding window with hash setsFixed-length window hashing

Repeated DNA Sequences

The DNA string s consists of the characters 'A', 'C', 'G', and 'T'. Return all 10-letter-long substrings that occur more than once in s. You may return the answer in any order.

Open official problem prompt ↗

In plain English

Report every distinct 10-character DNA sequence that appears at least twice anywhere in the string.

Picture it like this

Like scanning a long text with a fixed 10-character viewfinder, jotting each snippet on a 'seen' list; the moment a snippet reappears you copy it to a 'duplicates' list, and the duplicates list ignores repeats of repeats.

Example

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Why: The 10-letter windows 'AAAAACCCCC' and 'CCCCCAAAAA' each appear at two different starting positions; no other 10-mer repeats.

Constraints

1 <= s.length <= 10^5s[i] is either 'A', 'C', 'G', or 'T'

Pattern lesson

See the pattern, then code

Fixed-length window hashing

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Every candidate is exactly 10 characters long, so there are at most n-9 windows; recording each window as we slide lets us flag the second time we ever see one.

New words, made simpleKnow these before the algorithm

k-mer: A substring of fixed length k; here every window is a 10-mer.
Sliding window: A contiguous range of fixed size that moves one position at a time across the input.
Hash set membership: Average O(1) test for whether an element has been recorded before.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Compare all pairs of windows

Far too slow at n = 10^5.

For every pair of start indices compare the two 10-mers.

Time O(n^2)Space O(1)

Best choiceTwo hash sets (seen / repeated)

Linear and simple; the repeated set naturally de-duplicates output.

Slide the window once, recording seen windows and promoting a window to the result the second time it appears.

Time O(n)Space O(n)

Rolling hash / bit encoding

Cuts the constant factor and per-key space; a good optimization if substring slicing is a concern.

Encode each 10-mer into a 20-bit integer (2 bits per base) and slide in O(1) per step.

Time O(n)Space O(n)

The rule we keep true

Invariant

After processing index i, 'seen' contains every 10-mer starting at positions 0..i, and 'repeated' contains exactly those 10-mers that have already appeared at least twice.

Why this is correct

Reasoning

A substring occurs more than once if and only if, at some point during the scan, it is already present in 'seen' when encountered again; adding it to a set (not a list) ensures each duplicate string is reported exactly once.

The algorithm in three movesSay these aloud before coding

1Slide a length-10 window across s from index 0 to len(s)-10

window[0:10] = 'AAAAACCCCC' added to seen

2Look up the current window in a 'seen' set

later 'AAAAACCCCC' seen again -> repeated

3If it was already seen, add it to a 'repeated' set (a set prevents duplicate outputs)

'CCCCCAAAAA' likewise repeats

4Otherwise record it as seen

5Return the repeated set as a list

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads[0:10]='AAAAACCCCC'

2 · AskIn seen?

3 · Update stateseen = {'AAAAACCCCC'}

4 · ResultNo -> record it

Key takeaway

The first length-10 window 'AAAAACCCCC' is the initial entry recorded in the seen set.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Two sets
'seen' tracks all windows; 'repeated' collects the answer without duplicates.
2
Lines 4-5Slide the window
range(len(s)-9) yields every valid length-10 start index.
3
Lines 6-9Seen-or-record
Promote to repeated on the second sighting, otherwise mark as seen.
4
Lines 10Return
Convert the repeated set to a list; order is unconstrained.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Strings shorter than 10 yield an empty list (the loop range is empty)
A window repeating three or more times still appears once in the output
All-identical strings like 'AAAAAAAAAAA' report a single repeat
No repeats returns an empty list

Common beginner mistakes

Using range(len(s)) and slicing past the end, producing short final windows
Collecting results in a list, which double-counts windows seen 3+ times
Off-by-one so the last valid window at index len(s)-10 is skipped
Assuming a specific output order that LeetCode does not require

Check your understanding

Why do we need a separate 'repeated' set rather than just returning windows found in 'seen'?

Repeated DNA Sequences

Repeated DNA Sequences

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search