Domain 2MediumCORE

Repeated DNA Sequences

We are given a DNA sequence s consisting of characters 'A', 'C', 'G', and 'T'. Our goal is to identify all unique 10-letter substrings that appear more than once in the input string.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Bit Manipulation

187. Repeated DNA Sequences

Model: qwen3.5:9b
Topics: Hash Table,Bit Manipulation
FAANG asked: 1
Acceptance rate: 41.7%


Problem Breakdown

We are given a DNA sequence s consisting of characters ‘A’, ‘C’, ‘G’, and ‘T’. Our goal is to identify all unique 10-letter substrings that appear more than once in the input string.

Inputs: A single string s. Outputs: A list containing every distinct substring (length 10) found at least twice. The order of elements does not matter, and each repeated sequence should be listed exactly once in the result set.

Constraints & Edge Cases:

  • Length Constraint: 1≤s.length≤1051 \le s.length \le 10^5. This implies an O(N)O(N) or close-to-linear solution is required; quadratic solutions will time out.
  • Empty/Short Input: If s has fewer than 10 characters, no valid substrings exist. The loop range must handle this gracefully to return an empty list without errors.
  • Duplicates in Output: We need a set of unique repeated sequences for the output, not every occurrence index or duplicate entries if they appear multiple times consecutively (handled by using sets).

Intuition

The core task is frequency counting on fixed-length windows.

  1. Brute Force Approach: One might think of extracting all substrings and comparing them pairwise or using nested loops to check if one substring exists elsewhere in the string. This would be O(N2)O(N^2) because there are roughly NN substrings, and checking existence naively takes time proportional to length (or number of other substrings). Given N=105N=10^5, this is too slow (≈1010\approx 10^{10} operations).
  2. Hash Table Insight: We need a way to store seen sequences for constant-time lookup. A Hash Map or Set allows us to check if we’ve encountered a specific substring before in O(1)O(1) average time (assuming string hashing is efficient, which it is for fixed length 10).
  3. Optimization Note: While the problem lists “Bit Manipulation” as a related topic—suggesting one could map ‘A’, ‘C’, ‘G’, ‘T’ to bits and pack them into an integer (since 410=2204^{10} = 2^{20} fits in standard integers)—Python handles string hashing very efficiently. For readability and maintainability, using strings as keys is acceptable here unless memory constraints are extremely tight. I will use a Set-based approach for clarity.

Approach

We can solve this with a single pass sliding window:

  1. Initialize two sets: seen to track substrings we’ve encountered at least once, and repeated (or result set) to store those that appear more than once.
  2. Iterate through the string using an index ii from 00 up to len(s)−10len(s) - 10. This ensures every window of length 10 is valid. In Python’s range, this corresponds to range(len(s) - 9) because range excludes the stop value, so we iterate indices 0…len(s)−100 \dots len(s)-10.
  3. Extract the substring s[i : i+10]. Since the window size (10) is constant, slicing takes amortized O(1)O(1) time relative to input length NN, though it creates a new string object of fixed memory cost.
  4. Check if this substring exists in our seen set:
    • If yes: It’s a duplicate we’ve already recorded once before. Add it to our result collection (repeated). We don’t need to increment a counter; just knowing it appeared twice is sufficient for the output requirement (unique sequences). Since repeated is a set, adding an existing string does nothing further, ensuring uniqueness in the final list.
    • If no: Mark this substring as seen by adding it to seen.
  5. After iterating through all windows, convert the repeated set into a list and return it.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the length of string s. We iterate once over the string. String slicing takes constant time relative to fixed window size (10), and hashing/insertion into sets are amortized O(1)O(1). Thus, total operations scale linearly with input size.
  • Space Complexity: O(N)O(N) where NN is the length of s. In the worst case (all substrings unique within the string’s capacity before repeating), we store roughly (N−9)(N-9) entries in our sets. Since each entry has a fixed maximum length (L=10L=10) and alphabet size, space scales linearly with input size as well. The claim of storing “roughly half” is incorrect; it can be proportional to the full number of windows minus 9.

Solution

def findRepeatedDnaSequences(s: str) -> list[str]:
    seen = set()
    repeated = set()
    
    # Iterate up to len - 10 because we need a window of size 10 starting at i
    for i in range(len(s) - 9): 
        sub = s[i : i+10]
        
        if sub in seen:
            repeated.add(sub)
        else:
            seen.add(sub)
            
    return list(repeated)

Edge Cases Handled

  • String length < 10: The loop range(len(s) - 9)