Repeated DNA Sequences
A DNA string is composed of the letters A, C, G and T. Given such a string, return every length-10 substring that appears more than once anywhere in the string.
- 1 ≤ s.length ≤ 10^5
- s[i] ∈ {A, C, G, T}
- Fixed window length 10
- Need to detect substrings already *seen*
- Alphabet of 4 letters — each window fits in 20 bits
Whenever a brute force re-scans earlier elements to check membership, count, or a complement, a hash table answers the same question in expected O(1) and turns O(n^2) into O(n). Grouping problems reduce to choosing a canonical key (a sorted string, a character-count tuple) and bucketing by it.
Slide a window of length 10 across the string and record each window in a hash set of seen windows; if a window is already present, add it to a result set. Storing raw substrings costs O(10) per step, which is fine here. For a tighter version, encode each letter in 2 bits and maintain a 20-bit rolling integer for the window, so hashing becomes constant time and memory-light.
- A general rolling hash (Rabin-Karp) handles arbitrary alphabets and window lengths; a suffix array can find all repeated substrings but is overkill for a fixed length.