algoadvance

The problem “Repeated DNA Sequences” asks you to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. A DNA sequence is composed of a series of nucleotides represented by the characters ‘A’, ‘C’, ‘G’, and ‘T’.

You need to:

  1. Identify all 10-letter-long sequences that appear more than once in the given string.
  2. Return these sequences in the form of a list.

Clarifying Questions

  1. Input Length: What is the maximum length of the DNA sequence string?
  2. Case Sensitivity: Are the DNA sequences case-sensitive?
  3. Multiple Occurrences: Should the sequences be listed with all their positions, or just be identified if they appear more than once?

For the sake of this problem, we will assume the input string could be up to 10^5 characters (as typical for coding challenges), is case-sensitive, and we just need to list the sequences without worrying about their positions.

Strategy

  1. Sliding Window: Use a sliding window of size 10 to traverse through the string.
  2. Hashing: Use a hash set to keep track of sequences we’ve seen and a second set to keep track of sequences that we’ve seen more than once.
  3. Result Collection: Store sequences that appear more than once in a list.

By using sets, we can efficiently check for repeating sequences.

Time Complexity

Python Code

def findRepeatedDnaSequences(s: str):
    if len(s) < 10:
        return []

    seen, repeated = set(), set()
    for i in range(len(s) - 9):
        sequence = s[i:i + 10]
        if sequence in seen:
            repeated.add(sequence)
        else:
            seen.add(sequence)
    
    return list(repeated)

# Example usage
dna_sequence = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
print(findRepeatedDnaSequences(dna_sequence))  # Output: ["AAAAACCCCC", "CCCCCAAAAA"]

Explanation

  1. Edge Case Handling: If the string length is less than 10, immediately return an empty list since it’s impossible to have 10-letter sequences.
  2. Sliding Window: Use a range-based loop to construct 10-letter substrings and move one character at a time.
  3. Tracking and Recording:
    • Use a set seen to record all the 10-letter sequences we come across.
    • Use another set repeated to record sequences that appear more than once.
  4. Finally, convert the repeated set to a list as the output.

This solution efficiently solves the problem by ensuring that all operations with sets (insertion, membership test) are performed in average O(1) time.

Try our interview co-pilot at AlgoAdvance.com