Repeated DNA Sequences

82.2k
0

Given a DNA string s, return all 10-letter-long substrings that occur more than once. The answer can be returned in any order.

Example 1

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

Explanation: Both "AAAAACCCCC" and "CCCCCAAAAA" appear more than once in the DNA string.

Example 2

Input: s = "AAAAAAAAAAAAA"

Output: ["AAAAAAAAAA"]

Explanation: The substring "AAAAAAAAAA" appears multiple times, but it should be added only once in the answer.

Brute Force Approach

Every valid answer must be a substring of exactly length 10. So instead of checking all substring lengths, only one fixed-size window matters. Start from index 0, take the next 10 characters, then move one step forward and repeat.

Now the question becomes simple: “Has this 10-letter sequence appeared before?”

A seen set can answer that quickly. But if the same repeated sequence appears many times, it should still be added to the answer only once. That is why a second set, repeated, is used.

Algorithm

  • If the string length is less than 10, return an empty answer because no valid 10-letter substring can exist.

  • Create a seen set to store every 10-letter sequence found for the first time.

  • Create a repeated set to store sequences that have already repeated. This prevents adding the same answer again and again.

  • Slide a window of size 10 from left to right. This checks every possible DNA sequence of the required length.

  • If the current sequence is already in seen, add it to repeated because it has appeared at least twice.

  • Otherwise, add it to seen because this is the first time that sequence has appeared.

  • Return all strings from the repeated set.

Dry Run

Compute Ncr Brute Dry Run

Compute Ncr Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Finds all 10-letter DNA sequences
that appear more than once.
*/
vector<string> findRepeatedDnaSequences(string s) {
// Stores sequences that have appeared at least once.
unordered_set<string> seen;
// Stores repeated sequences only once.
unordered_set<string> repeated;
/*
If the string has fewer than 10 characters,
no 10-letter DNA sequence can be formed.
*/
if (s.length() < 10) {
return {};
}
for (int i = 0; i <= (int)s.length() - 10; i++) {
// Current window is the 10-letter DNA sequence being checked.
string sequence = s.substr(i, 10);
/*
If this sequence was already seen,
it is a repeated DNA sequence.
*/
if (seen.count(sequence)) {
repeated.insert(sequence);
} else {
/*
If this is the first appearance,
store it for future checks.
*/
seen.insert(sequence);
}
}
return vector<string>(repeated.begin(), repeated.end());
}
};
int main() {
// Driver code starts
string s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
Solution obj;
vector<string> answer = obj.findRepeatedDnaSequences(s);
for (string sequence : answer) {
cout << sequence << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(n) because there are n - 9 windows, and each substring has fixed length 10.

Space Complexity: O(n) because the sets can store many different 10-letter sequences.

Optimal Approach

The hash set approach stores actual strings. That is easy to understand, but DNA has a special property: it uses only 4 characters.

Four characters can be represented using only 2 bits:

A = 0, C = 1, G = 2, T = 3

A DNA sequence of length 10 therefore needs only 20 bits. So each 10-letter substring can be represented as one integer.

As the window moves, the bitmask is updated by adding the new character and keeping only the last 20 bits. This avoids building a new substring just for checking whether the sequence was seen.

Algorithm

  • If the string length is less than 10, return an empty answer because no valid window exists.

  • Convert every DNA character into a small number from 0 to 3. This works because there are only four possible DNA letters.

  • Keep a rolling integer mask that represents the latest DNA window.

  • For each character, shift the current mask left by 2 bits and add the encoded value of the new character. This makes room for the new DNA letter.

  • Keep only the last 20 bits of the mask because only the latest 10 characters matter.

  • Once at least 10 characters have been processed, check whether this mask has appeared before.

  • If the mask is already seen, add the current 10-letter substring to the answer set.

  • Otherwise, store the mask as seen for future windows.

Dry Run

Compute Ncr Optimal Dry Run

Compute Ncr Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Converts a DNA character into a 2-bit value.
*/
int getValue(char ch) {
// A is represented by 0.
if (ch == 'A') {
return 0;
}
// C is represented by 1.
if (ch == 'C') {
return 1;
}
// G is represented by 2.
if (ch == 'G') {
return 2;
}
// T is represented by 3.
return 3;
}
public:
/*
Finds repeated DNA sequences using
a compact 20-bit rolling mask.
*/
vector<string> findRepeatedDnaSequences(string s) {
/*
If the string has fewer than 10 characters,
no valid DNA sequence can be formed.
*/
if (s.length() < 10) {
return {};
}
// Stores masks that have appeared at least once.
unordered_set<int> seen;
// Stores repeated strings only once.
unordered_set<string> repeated;
// Mask stores the latest 10-character DNA window.
int mask = 0;
// This keeps only the rightmost 20 bits.
int lastTwentyBits = (1 << 20) - 1;
for (int i = 0; i < s.length(); i++) {
/*
Shift left to make space for the new character,
then add the 2-bit value of that character.
*/
mask = ((mask << 2) | getValue(s[i])) & lastTwentyBits;
/*
A complete 10-letter window is available
only after index 9.
*/
if (i >= 9) {
// Current 10-letter sequence is needed only for the answer.
string sequence = s.substr(i - 9, 10);
/*
If the same mask appeared before,
this DNA sequence is repeated.
*/
if (seen.count(mask)) {
repeated.insert(sequence);
} else {
/*
If this mask is new, store it so
later windows can be compared with it.
*/
seen.insert(mask);
}
}
}
return vector<string>(repeated.begin(), repeated.end());
}
};
int main() {
// Driver code starts
string s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
Solution obj;
vector<string> answer = obj.findRepeatedDnaSequences(s);
for (string sequence : answer) {
cout << sequence << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(n) because each character is processed once.

Space Complexity: O(n) because the seen masks and repeated answers may grow with the input size.

Interview follow-up Questions

One set tracks sequences seen before, and the other set prevents duplicate repeated sequences from being added many times.

String

Read Similar Blogs

TrieRecursionArraysData StructuresString

Word Search II

Given a 2D board of characters and a list of words, return all words that can be formed on the board. Each word must be built by moving to horizontally or vertically adjacent cells. The same cell c...

100.8k
StringRecursionArrays

Introduction to String Advanced

1. Basic Pattern Matching Problem Suppose a word needs to be searched inside a larger sentence or string. The goal is to find all starting positions where the smaller pattern exactly matches a part...

66.8k
String

Introduction to Prefix-Suffix in String

Given a string s , find the length of the longest proper prefix that is also a suffix. A proper prefix means the whole string itself is not allowed. So if s = "aaaa" , the answer is 3 , because "aa...

81.6k
Comments0