Problem Statement
Repeated DNA Sequences
DNA is written using only four letters: 'A', 'C', 'G', and 'T'. You are given a long string s made of these letters. Your job is to find every 10-letter chunk (a substring) that shows up more than once anywhere in the string, and return all of them. A substring is just a stretch of letters taken from the original, side by side, like reading 10 letters in a row starting at some position. The clean way to solve this is with a hash set. A set is like a guest list at a door: you can add a name, and you can instantly check "is this name already on the list?" without scanning the whole thing. Here is the plan: slide a 10-letter window across the string, and for each chunk ask the set "have I seen you before?" If yes, that chunk is a repeat, so we save it. We use two sets, one for "chunks I have seen" and one for "repeats to report," so each repeated sequence gets reported exactly once even if it appears three or four times.
Signals to notice
Brute force first
Check every pair of 10-letter substrings — O(n²).
The key insight
Slide a window of size 10. Hash each window into a set. If already seen, it's a duplicate. O(n).
Trace it on s="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" (len 32)
init: seen={}, repeated={}; loop i runs 0..22 (len 32 - 10)
i=0: seq="AAAAACCCCC" not in seen -> seen={AAAAACCCCC}; i=1..4 add more new windows
i=5: seq="CCCCCAAAAA" new -> seen+={CCCCCAAAAA}; i=6..9 add more new windows
i=10: seq="AAAAACCCCC" already in seen -> repeated={AAAAACCCCC}
i=11: seq="AAAACCCCCC" new (6th C) -> seen+={AAAACCCCCC}; i=12..14 new
i=15: seq="CCCCCCAAAA" new (6 C's) -> seen+={CCCCCCAAAA}
i=16: seq="CCCCCAAAAA" already in seen -> repeated={AAAAACCCCC, CCCCCAAAAA}
i=17..22: G/T-tail windows all new; return list(repeated)=["AAAAACCCCC","CCCCCAAAAA"]What must stay true
A hash set of seen substrings gives O(1) duplicate detection per window position.
Shape of the loop
seen, repeated = empty sets
for i from 0 to len(s) - 10:
seq = s[i : i+10]
if seq in seen: repeated.add(seq)
else: seen.add(seq)
return list(repeated)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Using two sets: 'seen' and 'result' — prevents adding the same duplicate to the result multiple times.