Repeated DNA Sequences

Medium
1201.

Repeated DNA Sequences

Repeated DNA Sequences is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and LinkedIn interviews.

A DNA strand is written as a string over the letters A, C, G and T.

Given a strand s, return every substring of length exactly 10 that occurs more than once in s (occurrences may overlap). Each such substring is listed once, and the list is sorted in ascending lexicographic order. Return an empty list if there is none.

Example 1

Input
s = "ACGTTGCAACACGTTGCAACGT"
Output
["ACGTTGCAAC"]
Explanation
`ACGTTGCAAC` starts at indices 0 and 10.

Example 2

Input
s = "CCCCCCCCCCCC"
Output
["CCCCCCCCCC"]
Explanation
Overlapping occurrences at 0, 1 and 2 count.

Example 3

Input
s = "GATTACA"
Output
[]

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is one of 'A', 'C', 'G', 'T'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Repeated DNA Sequences — Solution in Python, Java & C++

Repeated DNA Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Repeated DNA Sequences is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and LinkedIn interviews.

Problem statement

A DNA strand is written as a string over the letters A, C, G and T.

Given a strand s, return every substring of length exactly 10 that occurs more than once in s (occurrences may overlap). Each such substring is listed once, and the list is sorted in ascending lexicographic order. Return an empty list if there is none.

Example 1

Input: s = "ACGTTGCAACACGTTGCAACGT"
Output: ["ACGTTGCAAC"]
Explanation: `ACGTTGCAAC` starts at indices 0 and 10.

Example 2

Input: s = "CCCCCCCCCCCC"
Output: ["CCCCCCCCCC"]
Explanation: Overlapping occurrences at 0, 1 and 2 count.

Example 3

Input: s = "GATTACA"
Output: []

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is one of 'A', 'C', 'G', 'T'

Hints for Repeated DNA Sequences

  1. Hint 1

    Slide a window of length 10 across s and count each window you see.

  2. Hint 2

    A hash map from window to count finds the repeats in one pass; report a window the moment its count reaches 2 so it is listed once.

  3. Hint 3

    With four letters a window fits in 20 bits (2 bits per letter), so it can be kept as an integer and updated in O(1) per step.

How to solve Repeated DNA Sequences

Every candidate is one of the n − 9 windows of length 10, so counting windows in a hash map finds exactly the repeated ones.

Approach

  1. For each start i from 0 to n − 10, take the window s[i..i+9].
  2. Increment its count; when the count becomes exactly 2, append the window to the answer.
  3. Sort the answer.
  4. (Optional) Encode A, C, G, T as 0–3 and keep the window as a 20-bit integer: shift left by 2, add the new letter, mask to 20 bits. Because A < C < G < T, sorting the codes numerically sorts the strings too.

Why it works

A length-10 substring that occurs twice is, by definition, two windows with equal content, so it reaches count 2 in the map; adding it only at that moment lists each repeated sequence exactly once no matter how many more times it appears.

Complexity

  • Time — O(n · 10) with string keys, O(n) with the rolling 20-bit code (plus sorting the answer)
  • Space — O(n)

Pitfalls

  • Adding a window every time its count is ≥ 2 lists sequences that occur three times twice.
  • Strings shorter than 10 have no windows — make sure the loop bound does not go negative.
  • Occurrences may overlap (CCCCCCCCCCC repeats CCCCCCCCCC); do not skip ahead after a match.

Reference solution

Python

from typing import List

def findRepeatedDnaSequences(s: str) -> List[str]:
    seen = {}
    res = []
    for i in range(len(s) - 9):
        t = s[i:i + 10]
        c = seen.get(t, 0) + 1
        seen[t] = c
        if c == 2:
            res.append(t)
    res.sort()
    return res

Java

public static String[] findRepeatedDnaSequences(String s) {
    Map<String, Integer> seen = new HashMap<>();
    List<String> res = new ArrayList<>();
    for (int i = 0; i + 10 <= s.length(); i++) {
        String t = s.substring(i, i + 10);
        int c = seen.getOrDefault(t, 0) + 1;
        seen.put(t, c);
        if (c == 2) res.add(t);
    }
    Collections.sort(res);
    return res.toArray(new String[0]);
}

C++

vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<string, int> seen;
    vector<string> res;
    for (int i = 0; i + 10 <= (int)s.size(); i++) {
        string t = s.substr(i, 10);
        if (++seen[t] == 2) res.push_back(t);
    }
    sort(res.begin(), res.end());
    return res;
}

JavaScript

var findRepeatedDnaSequences = function(s) {
    var seen = new Map();
    var res = [];
    for (var i = 0; i + 10 <= s.length; i++) {
        var t = s.substring(i, i + 10);
        var c = (seen.has(t) ? seen.get(t) : 0) + 1;
        seen.set(t, c);
        if (c === 2) res.push(t);
    }
    res.sort();
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets