Problem 35.6 · Advanced String AlgorithmsMedium

Repeated DNA Sequences

PatternString Matching (KMP, Z, Rolling Hash)Sliding Window: Fixed Size Bit Manipulation

What it teaches: A rolling 2-bit-per-letter code makes each 10-letter window a 20-bit integer.

Practise it on judges as “Repeated DNA Sequences”.

In plain words

Slide a window 10 letters wide along the DNA string. Keep a notebook of every 10-letter piece you've seen. If you meet a piece that's already in the notebook, it repeats, so add it to the answer (once).

Return every 10-letter piece that occurs more than once. Example: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" → [AAAAACCCCC, CCCCCAAAAA].

The problem

Return every 10-letter substring of a DNA string (letters A, C, G, T) that occurs more than once, in any order.

Example 1

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: [AAAAACCCCC, CCCCCAAAAA]

Constraints

1 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Fixed-length substrings, find repeats

These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"	["AAAAACCCCC","CCCCCAAAAA"]
2	s = "AAAAAAAAAAAAA"	["AAAAAAAAAA"]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Rolling bit code · O(n)2. Substring set · O(10 n)

Rolling bit code

Time O(n) Space O(n)

code = ((code << 2) | letter) & 0xFFFFF. Track seen codes and codes already reported.

Approach 1

import java.util.*;

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Map<Character, Integer> bits = Map.of('A', 0, 'C', 1, 'G', 2, 'T', 3);
        Set<Integer> seen = new HashSet<>(), reported = new HashSet<>();
        List<String> out = new ArrayList<>();
        int code = 0;
        for (int i = 0; i < s.length(); i++) {
            code = ((code << 2) | bits.get(s.charAt(i))) & 0xFFFFF;
            if (i < 9) continue;
            if (!seen.add(code) && reported.add(code)) out.add(s.substring(i - 9, i + 1));
        }
        return out;
    }
}

Verdict: A perfect hash: no collisions.

Substring set

Time O(10 n) Space O(10 n)

Put every 10-letter substring in a set; report repeats once.

▶ Dry run: A seen set and a repeated sets = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

repeated(list)

empty

Step 1/5i = 0: "AAAAACCCCC" is new, so it goes into the seen set.

Approach 2

import java.util.*;

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> seen = new HashSet<>(), repeated = new LinkedHashSet<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String w = s.substring(i, i + 10);
            if (!seen.add(w)) repeated.add(w);
        }
        return new ArrayList<>(repeated);
    }
}

Verdict: Simplest; more memory.

Before you submit

Edge cases and common mistakes

Test these inputs

Length under 10 (empty)
A sequence repeated three times (report once)

Mistakes people make

Reporting the same sequence several times.

Interview

Follow-up questions

What if the alphabet were larger or the window longer than 16 letters?

Connect the dots

Where this shows up in real systems

System Design · System 12.13 — Dropbox (Sync Engine)Rolling hashes find repeated chunks so only changed blocks are uploaded.

Command Palette