173. Repeated DNA Sequences
A DNA strand is written as a string s over the four letters A, C, G, and T. Slide a window of length 10 across the strand: every position produces one length-10 substring.
Return every length-10 substring that appears more than once anywhere in the strand. Each repeated substring is reported once, regardless of how many times it occurs.
To make the answer deterministic, return the repeated substrings in sorted (lexicographic) order. If nothing repeats, return an empty list.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Explanation: Both AAAAACCCCC and CCCCCAAAAA occur twice as 10-letter windows; sorted, A... comes before C....
Example 2:
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
Explanation: A run of 13 A's contains the window AAAAAAAAAA at several offsets, so it repeats.
Constraints:
- 0 ≤ s.length ≤ 10⁵
- s consists only of the characters A, C, G, and T
- The window length is fixed at 10
Hints:
There are only length-10 windows starting at positions 0 through n-10. Walk them one at a time.
Track how many times each window has been seen with a hash set (or map). The second time you meet a window, add it to the answer — but only once, even if it shows up a third or fourth time.
For a space-savvy version, pack each window into a small integer: two bits per base means a 10-letter window fits in 20 bits, and a sliding update is O(1) per step.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Expected output: ["AAAAACCCCC", "CCCCCAAAAA"]