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.
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; }}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.