⚡Flashcard Drill➔
NeetCode #126LC-187MediumArrays & Hashing
← Back to All Problems

#126 · #187 · Repeated DNA Sequences(重复的 DNA 序列)

📌 Problem Statement & Constraints

The DNA sequence is composed of 'A', 'C', 'G' and 'T'. Given a string s representing a DNA sequence, return all 10-letter-long substrings that occur more than once. Constraints: 1 <= s.length <= 10^5.

💡 Core Algorithmic Approaches

  1. Slide a window of length 10 across s and record each distinct substring in a hash set.
  2. The first time a substring is seen, add it to seen; the second time, add it to the result set.
  3. Using a set for the result deduplicates substrings that occur three or more times.
  4. The number of windows is n - 9, and each window costs O(1) to hash (a constant length of 10), so the total is O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        if len(s) < 10:
            return []
        seen = set()
        repeated = set()
        for i in range(len(s) - 9):        # windows of exactly length 10
            sub = s[i:i + 10]
            if sub in seen:
                repeated.add(sub)          # second sighting
            else:
                seen.add(sub)
        return list(repeated)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) with a constant window length: n - 9 windows, each hashed in O(1) because the length is fixed at 10.
💾 Space Complexity
O(n) for the seen set in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Using range(len(s) - 10): the last window would be missed; the correct bound is len(s) - 9.
  • Returning duplicates without deduplication: a substring occurring three times would appear twice in the output; hence the separate result set.
  • Appending to a list on every second sighting: same issue, and it also loses the set's O(1) membership test.
  • Encoding the substrings as integers for speed: a legitimate optimisation (2 bits per base), but unnecessary given the constant window length.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems