Repeated DNA Sequences
MedPrompt
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.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]Example 2:
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
Constraints:
1 <= s.length <= 105s[i]is either'A','C','G', or'T'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves a straightforward, nested-loop comparison. We take every possible 10-letter substring and compare it with every subsequent 10-letter substring in the sequence. A HashSet is used to store the found repeated sequences to ensure the final output contains only unique entries.
Algorithm
- Initialize an empty set
resultto store the unique repeated sequences. - Iterate through the string
swith an indexifrom the beginning up to the point where a 10-letter substring can be formed (s.length() - 10). - For each
i, extract the substringsub1 = s.substring(i, i + 10). - Start a nested loop with an index
jfromi + 1tos.length() - 10. - In the inner loop, extract the substring
sub2 = s.substring(j, j + 10). - If
sub1is equal tosub2, it means we have found a repeated sequence. Addsub1to theresultset. - To avoid redundant checks for
sub1, we can break the inner loop once a match is found. - After the loops complete, convert the
resultset into a list and return it.
Walkthrough
The brute-force method is the most intuitive way to solve the problem. We generate all possible 10-letter substrings starting from each index i. For each of these substrings, we then scan the rest of the string from index i+1 onwards to see if an identical substring exists. If a match is found, we add the substring to a HashSet to automatically handle duplicates in the final result. While simple, this method's performance degrades rapidly as the input string size increases due to its O(N^2) nature.
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public List<String> findRepeatedDnaSequences(String s) { int n = s.length(); if (n <= 10) { return new ArrayList<>(); } Set<String> result = new HashSet<>(); // Iterate through all possible start indices of a 10-letter substring for (int i = 0; i <= n - 10; i++) { String sub1 = s.substring(i, i + 10); // Compare with all subsequent 10-letter substrings for (int j = i + 1; j <= n - 10; j++) { String sub2 = s.substring(j, j + 10); if (sub1.equals(sub2)) { result.add(sub1); break; // Found a repeat, no need to check further for sub1 } } } return new ArrayList<>(result); }}Complexity
Time
O(N^2 * L)
Space
O(K * L)
Trade-offs
Pros
Simple to conceptualize and implement.
Does not require complex data structures.
Cons
Extremely inefficient with a quadratic time complexity, which will likely result in a 'Time Limit Exceeded' error for large inputs.
Performs a large number of redundant string comparisons.
A more optimized approach uses a HashSet to keep track of substrings we've already seen. We iterate through the string's 10-letter substrings only once. For each substring, we check if it's already in our seen set. If it is, we've found a repeat and add it to a separate repeated set. If it's not, we add it to the seen set. This avoids the expensive nested loop of the brute-force method.
Algorithm
- Initialize two hash sets:
seento store every unique 10-letter substring encountered, andrepeatedto store the substrings that appear more than once. - Iterate through the string
swith a single loop, from indexi = 0tos.length() - 10. - In each iteration, extract the 10-letter substring
current = s.substring(i, i + 10). - Attempt to add
currentto theseenset. Theaddmethod of aHashSetreturnsfalseif the element is already present. - If
seen.add(current)returnsfalse, it signifies that we have encountered this substring before, so it is a repeated sequence. Addcurrentto therepeatedset. - The
repeatedset automatically handles duplicates, so a sequence repeated three or more times is only added once. - After the loop finishes, convert the
repeatedset to a list and return it.
Walkthrough
This method improves upon the brute-force approach by leveraging the constant-time average complexity of hash set operations. We slide a window of length 10 over the string from left to right. For each 10-letter substring, we use two sets: seen and repeated. The seen set stores every unique substring we encounter. If we try to add a substring to seen and it's already there, we know it's a repeat. We then add this repeated substring to the repeated set. Using a set for the results ensures that even if a sequence is repeated multiple times (e.g., "AAAAAAAAAAA"), the result "AAAAAAAAAA" is only stored once.
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public List<String> findRepeatedDnaSequences(String s) { int n = s.length(); if (n <= 10) { return new ArrayList<>(); } Set<String> seen = new HashSet<>(); Set<String> repeated = new HashSet<>(); for (int i = 0; i <= n - 10; i++) { String sub = s.substring(i, i + 10); if (!seen.add(sub)) { // If add returns false, it means the substring was already in the set. repeated.add(sub); } } return new ArrayList<>(repeated); }}Complexity
Time
O((N - L) * L)
Space
O((N - L) * L)
Trade-offs
Pros
Much more efficient than the brute-force approach, with a linearithmic time complexity.
Easy to implement using standard library hash sets.
Cons
The time complexity is affected by the cost of creating and hashing substrings of length L, making it O(N*L) instead of O(N).
The space complexity can be high, as it requires storing the actual string objects in the hash set, which can consume significant memory for a large number of unique substrings.
The most optimal approach uses a rolling hash technique combined with bit manipulation. Each of the 4 DNA characters can be represented by 2 bits. Therefore, any 10-letter sequence can be encoded into a unique 20-bit integer. We can slide a window across the string, and for each step, we can calculate the new sequence's integer representation from the previous one in constant O(1) time using bitwise operations. This avoids creating new substrings and performs hashing much faster, leading to a true O(N) time complexity.
Algorithm
- Since the alphabet is small (A, C, G, T), map each character to a 2-bit integer (e.g., A->0, C->1, G->2, T->3).
- A 10-letter sequence can be uniquely represented by a 20-bit integer (10 letters * 2 bits/letter).
- Initialize two sets:
seento store the integer representations of encountered sequences, andoutputto store the actual repeated string sequences. - Calculate the integer representation for the first 10-letter window by iterating through its characters and using bitwise left-shift and OR operations.
- Add this first integer representation to the
seenset. - Now, iterate from the second character of the string to the end, 'rolling' the window one character at a time.
- In each step, update the integer representation in O(1) time: left-shift the current integer by 2, apply a 20-bit mask to remove the oldest character's bits, and OR with the new character's 2-bit value.
- If adding the new integer to
seenfails (i.e., it's a duplicate), add the corresponding 10-letter substring to theoutputset. - Finally, return the
outputset as a list.
Walkthrough
This approach is a highly optimized version of the rolling hash. By mapping each DNA character to a 2-bit number, we can represent any 10-letter sequence as a single 20-bit integer, which fits comfortably within a standard 32-bit int. This provides a perfect, collision-free hash.
The key is the 'rolling' update. Instead of recomputing the 20-bit integer for each substring, we can derive the next integer from the previous one in O(1) time. This is done by:
- Shifting the current integer left by 2 bits (
h << 2), which makes space for the new character and effectively starts the process of dropping the oldest character. - Applying a bitmask (
& ((1 << 20) - 1)) to ensure we only keep the 20 least significant bits, which completes the removal of the oldest character's bits. - Using a bitwise OR to add the 2 bits of the new character at the end of the window.
This method is significantly faster and more memory-efficient because we are manipulating and storing primitive integers instead of string objects.
import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set; class Solution { public List<String> findRepeatedDnaSequences(String s) { int n = s.length(); int L = 10; if (n <= L) { return new ArrayList<>(); } Map<Character, Integer> toInt = new HashMap<>() {{ put('A', 0); put('C', 1); put('G', 2); put('T', 3); }}; Set<Integer> seen = new HashSet<>(); Set<String> output = new HashSet<>(); int bitmask = (1 << (L * 2)) - 1; // A mask for 20 bits (10 letters * 2 bits) int currentHash = 0; // Calculate hash for the first window for (int i = 0; i < L; i++) { currentHash = (currentHash << 2) | toInt.get(s.charAt(i)); } seen.add(currentHash); // Roll the window over the rest of the string for (int i = 1; i <= n - L; i++) { // Update hash: shift left, mask to remove old bits, and add new bits currentHash = ((currentHash << 2) & bitmask) | toInt.get(s.charAt(i + L - 1)); if (!seen.add(currentHash)) { // If add returns false, the hash (and thus the sequence) has been seen before output.add(s.substring(i, i + L)); } } return new ArrayList<>(output); }}Complexity
Time
O(N - L)
Space
O(N - L)
Trade-offs
Pros
Optimal linear time complexity O(N).
Highly space-efficient as it stores compact integers in the 'seen' set instead of larger string objects.
Guaranteed no hash collisions due to the perfect mapping of sequences to integers.
Cons
The implementation is more complex and less intuitive than the previous approaches.
This specific bit manipulation technique is tailored to the problem's constraints (small alphabet, fixed length) and is not a general-purpose solution.
Solutions
Solution
public class Solution { public IList < string > FindRepeatedDnaSequences(string s) { var cnt = new Dictionary < string, int > (); var ans = new List < string > (); for (int i = 0; i < s.Length - 10 + 1; ++i) { var t = s.Substring(i, 10); if (!cnt.ContainsKey(t)) { cnt[t] = 0; } if (++cnt[t] == 2) { ans.Add(t); } } return ans; }}class Solution {public List<String> findRepeatedDnaSequences(String s) { Map<String, Integer> cnt = new HashMap<>(); List<String> ans = new ArrayList<>(); for (int i = 0; i < s.length() - 10 + 1; ++i) { String t = s.substring(i, i + 10); if (cnt.merge(t, 1, Integer : : sum) == 2) { ans.add(t); } } return ans; }}/** * @param {string} s * @return {string[]} */ var findRepeatedDnaSequences = function ( s ) { const cnt = new Map (); const ans = []; for ( let i = 0 ; i < s . length - 10 + 1 ; ++ i ) { const t = s . slice ( i , i + 10 ); cnt . set ( t , ( cnt . get ( t ) || 0 ) + 1 ); if ( cnt . get ( t ) === 2 ) { ans . push ( t ); } } return ans ; };class Solution {public: vector<string> findRepeatedDnaSequences(string s) { unordered_map<string, int> cnt; vector<string> ans; for (int i = 0, n = s.size() - 10 + 1; i < n; ++i) { auto t = s.substr(i, 10); if (++cnt[t] == 2) { ans.emplace_back(t); } } return ans; }};class Solution: # for encoded words repeated = set () # for encoded words result = [] # not encoded words # A => binary: 00 # C => binary: 01 # G => binary: 10 # T => binary: 11 mapping = { 'A' : 0 , 'C' : 1 , 'G' : 2 , 'T' : 3 } for i in range ( len ( s ) - 9 ): v = 0 for j in range ( i , i + 10 ): # every time, use the new 2 bits after shifting for current char v <<= 2 v |= mapping [ s [ j ]] if v in words and v not in repeated : repeated . add ( v ) result . append ( s [ i : i + 10 ]) words . add ( v ) return result ############ class Solution : def findRepeatedDnaSequences ( self , s : str ) -> List [ str ]: n = len ( s ) - 10 cnt = Counter () ans = [] for i in range ( n + 1 ): sub = s [ i : i + 10 ] cnt [ sub ] += 1 if cnt [ sub ] == 2 : ans . append ( sub ) return ans def findRepeatedDnaSequences(self, s: str) -> List[str]: words = set()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.