Repeated DNA Sequences
Find every 10-letter DNA substring that occurs more than once, each reported exactly once.
Open on LeetCode ↗Intuition
The trap is pushing a substring to the answer every time you see it again, so a sequence that appears three times lands in the output twice. You need two pieces of state, not one: a seen-set for 'have I hashed this before' and an added-set for 'is it already in the answer'. Only add a substring the moment it flips from seen-once to seen-twice, and never again after that. Since the window width is fixed at 10, there is no need for anything fancier than sliding a window and slicing -- no suffix structures required. The invariant is: seen tracks history, added tracks output membership, and they only agree at the transition moment.
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
Slide a fixed window
Walk i from 0 to len(s)-10 and take the 10-character substring s[i:i+10] at each position. Because the width never changes, a plain substring slice is enough; there's no need to maintain a rolling hash unless you want the O(1)-per-step optimization.
Track seen vs added separately
Keep a set of substrings already seen once. When a substring is encountered and it's already in the seen set but not yet in an added set, append it to the result and mark it added. If it's already been added, skip it silently -- this is what prevents duplicate entries in the output.
Return the result list
After the scan finishes, the result list contains each repeated 10-letter sequence exactly once, in the order its second occurrence was found. Order does not matter for correctness on LeetCode, only uniqueness does.
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