Solution: Repeated DNA Sequences

Discover how to identify repeated 10-letter DNA sequences in a string using an optimized sliding window approach combined with a rolling hash. This lesson guides you through encoding characters numerically, computing initial hashes, and updating these hashes efficiently to detect repetitions, enhancing your understanding of substring problems and hashing techniques.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using sliding window

Statement

A DNA sequence consists of nucleotides represented by the letters ‘A’, ‘C’, ‘G’, and ‘T’ only. For example, “ACGAATTCCG” is a valid DNA sequence.

Given a string, s, that represents a DNA sequence, return all the 10-letter-long sequences (continuous substrings of exactly 10 characters) that appear more than once in s. You can return the output in any order.

Constraints:

$1 \leq$ s.length $\leq 10^{3}$
s[i] is either 'A', 'C', 'G', or 'T'.

Solution

So far, you’ve probably brainstormed some approaches to solving this problem. Considering time complexity and implementation constraints, let’s explore some of these approaches and determine which to follow.

Naive approach

The naive approach to solving this problem would be to use a nested loop to check all possible 10-letter-long substrings in the given DNA sequence. Using a set, we would extract every possible substring of length 10 and compare it with all previously seen substrings. If a substring appears more than once, we add it to the result.

Specifically, we start by iterating through the string and extracting every substring of length 10. For each substring, we check if it has already been seen before. We store it in a separate set to track repeated sequences if it has. If not, we add it to the set of seen substrings. Finally, we return all repeated sequences as a list. This method is simple to understand but inefficient because checking each substring against previously seen ones takes much time, making it slow for large inputs.

We extract all k-length (where $k$ = 10) substrings from the given string s, which has length n. This means we extract $(n - k + 1)$ substrings. Each substring extraction takes $O(k)$ time. Checking whether a substring is in a set (average case) takes $O(1)$ , but in the worst case (hash collisions), it takes $O(n - k + 1)$ comparisons. Inserting a new substring into the set takes $O(1)$ on average, but worst case $O(n - k + 1$ ). Therefore, the overall time complexity becomes $O((n-k) × k)$ ...