Repeated DNA Sequences
Medium · Bit Manipulation · Hash Table · String · Bit Manipulation · Sliding Window · Rolling Hash
Problem
A DNA strand is written as a string s over the letters 'A', 'C', 'G' and 'T'.
Return every substring of length exactly 10 that occurs more than once in s. Occurrences may overlap. List each such substring only once; the order of the result does not matter.
Examples
Input: s = "ACGTACGTACGTAC" Output: ["ACGTACGTAC"]
The windows starting at 0 and at 4 are both ACGTACGTAC.
Input: s = "AAAAAAAAAAA" Output: ["AAAAAAAAAA"]
The two overlapping windows of ten A are identical; it is reported once.
Input: s = "ACGT" Output: []
The string is shorter than 10, so there is no window.
Constraints
- 1 <= len(s) <= 10^5
- s[i] is 'A', 'C', 'G' or 'T'
Approaches
- Baseline: compare every pair of windows — time O(n² · 10), space O(k) for k results
Follow-up
The 2-bit code is a perfect hash: different windows never share a code, which a general string hash cannot promise. For longer windows or larger alphabets a polynomial rolling hash (Rabin–Karp) plays the same role, with a check on matches. The use cases count the most common window and find the longest stretch that repeats, where the window length itself has to be searched.
Related problems
Start free on Cariara · Coding problems · System design studio
