187. Repeated DNA Sequences

2024, Oct 31 2 mins read

1. Description

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

For example, “ACGAATTCCG” is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

2. Example

Example 1

Input: s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
Output: [“AAAAACCCCC”,“CCCCCAAAAA”]

Example 2

Input: s = “AAAAAAAAAAAAA”
Output: [“AAAAAAAAAA”]

3. Constraints

1 <= s.length <= 10^5
s[i] is either ‘A’, ‘C’, ‘G’, or ‘T’.

4. Solutions

Sliding Window & Hash Table

n = str.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<string> findRepeatedDnaSequences(const string &str) {
        unordered_map<char, int> binary = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        const int sequence_length = 10;
        if (str.size() < sequence_length) {
            return {};
        }

        int sequence = 0;
        for (int i = 0; i < sequence_length; ++i) {
            sequence = (sequence << 2) | binary[str[i]];
        }
        unordered_map<int, int> sequence_count = {{sequence, 1}};
        vector<string> repeated_DNA;
        for (int i = sequence_length; i < str.size(); ++i) {
            sequence = (sequence << 2) & ((1 << (sequence_length * 2)) - 1) | binary[str[i]];
            ++sequence_count[sequence];
            if (sequence_count[sequence] == 2) {
                repeated_DNA.emplace_back(str.substr(i - sequence_length + 1, sequence_length));
            }
        }

        return repeated_DNA;
    }
};

Search

Tags