A DNA string contains only the letters A, C, G and T. Return every 10-letter substring that occurs more than once, each reported once, in any order.
Before you code
Slicing every window and putting the strings in a set works, at O(10n). With four letters, how many bits does one letter need, and does a whole 10-letter window fit in an integer?
Hints
- Map A, C, G and T to 0, 1, 2 and 3: two bits each, so a window fits in 20 bits.
- Roll the window: shift left by 2, add the new letter, and mask to the low 20 bits.
- Keep a set of windows seen once and a set of windows already reported.
Production & complexity notes
When solving Repeated DNA sequences on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Rolling hash and Rabin-Karp to reinforce the underlying pattern.
What it practices
Rolling a window's value in constant time, from Rolling hash and Rabin-Karp.