What is the best pattern for Repeated DNA Sequences?

The cleanest pattern is a fixed-length sliding window backed by hashing. Because every target substring is exactly 10 characters long, you only need to scan those windows and record which ones have appeared before.

Why does overlap matter in this problem?

The repeated 10-letter DNA sequences can overlap heavily, especially in inputs like "AAAAAAAAAAAAA". You cannot skip ahead after a match because the next valid repeated window may start just one position later.

Should I use strings or bit manipulation for LeetCode 187?

Start with strings and sets if you want the fastest correct explanation. Use bit manipulation when you want a tighter implementation that updates the 10-letter window as a compact rolling state rather than rebuilding substrings.

Why do we need two sets or an equivalent repeated marker?

One set tracks whether a 10-letter sequence has appeared before, and the second prevents duplicate answers. Without that separation, a sequence that appears three times would be appended multiple times even though the output should list it once.

What edge case is easiest to miss in Repeated DNA Sequences?

The easiest miss is when the input length is less than 10, because no valid DNA substring can exist. Another frequent miss is mishandling the encoded window mask, which silently corrupts later matches.

#187

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

重复的DNA序列

DNA序列由一系列核苷酸组成，缩写为 'A' , 'C' , 'G' 和 'T' .。例如， "ACGAATTCCG" 是一个 DNA序列。在研究 DNA 时，识别 DNA 中的重复序列非常有用。给定一个表示 DNA序列的字符串 s ，返回所有在 DNA 分子中出现不止一次的长度为 1…

哈希表字符串位运算滑动窗口滚动哈希

题目描述

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：

0 <= s.length <= 10⁵
s[i]=='A'、'C'、'G' or 'T'

lightbulb

解题思路

方法一：哈希表

我们定义一个哈希表 $cnt$ ，用于存储所有长度为 $10$ 的子字符串出现的次数。

遍历字符串 $s$ 的所有长度为 $10$ 的子字符串，对于当前子字符串 $t$ ，我们更新其在哈希表中对应的计数。如果 $t$ 的计数为 $2$ ，我们就将它加入答案。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n \times 10)$ ，空间复杂度 $O(n \times 10)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        cnt = Counter()
        ans = []
        for i in range(len(s) - 10 + 1):
            t = s[i : i + 10]
            cnt[t] += 1
            if cnt[t] == 2:
                ans.append(t)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They expect you to notice the substring length is fixed at 10, which strongly suggests a sliding window instead of variable-length scanning.
question_mark
They want you to handle overlap correctly, because repeated DNA blocks can start one index apart and still count.
question_mark
They may push for a bit manipulation upgrade after the hash-set solution, especially if they mention A, C, G, and T as a tiny alphabet.

warning

常见陷阱

外企场景

error
Adding a sequence to the result every time it repeats, which produces duplicates when the same 10-letter block appears many times.
error
Forgetting the early return when s.length < 10, which leads to unnecessary logic around impossible windows.
error
Breaking the rolling encoding by not masking out old bits, causing the running state to represent more than 10 characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the count of each repeated 10-letter DNA sequence instead of only the unique repeated strings.
arrow_right_alt
Change the target length from 10 to k, which keeps the same sliding-window idea but changes the mask width in the encoded version.
arrow_right_alt
Process a stream of DNA characters online, where the last 10 characters define the current window and repeats are detected incrementally.

help

常见问题

外企场景

继续练习

#1016 子串能表示从 1 到 N 数字的二进制串 #76 最小覆盖子串 #30 串联所有单词的子串