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
- Slide a window of length 10 across
sand record each distinct substring in a hash set. - The first time a substring is seen, add it to
seen; the second time, add it to the result set. - Using a set for the result deduplicates substrings that occur three or more times.
- 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 islen(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.