重复的 DNA 序列如何用位编码优化？为什么 10 个字符只需要 20 位？

简化版

DNA 字符只有 A/C/G/T 四种，可以用 2 位编码一个字符。长度为 10 的 DNA 片段只需要 20 位，用滚动位掩码维护最近 10 个字符的编码，把出现过一次和重复出现的编码分别放入集合即可。

详细版

映射可设为 A=0,C=1,G=2,T=3。遍历字符串时，执行 mask = ((mask << 2) | code) & ((1 << 20) - 1)，表示加入新字符并保留最近 10 个字符。第 10 个字符开始，每个 mask 对应一个长度 10 的子串。

用 seen 记录出现过的 mask，用 duplicated 或结果集合避免重复加入答案。时间复杂度 O(n)，空间复杂度 O(n)。

完整版教学

一、为什么 DNA 可以压成位编码

DNA 题只包含 4 种字符：A,C,G,T。4 种状态刚好能用 2 个 bit 表示：

字符	编码
A	`00`
C	`01`
G	`10`
T	`11`

因此长度 10 的字符串需要：

10 * 2 = 20 bit

一个 int 足够存下这个片段。

二、滚动窗口如何更新 mask

每读入一个新字符，就把旧 mask 左移 2 位，并把新字符编码放到最低 2 位：

mask = (mask << 2) | code

但我们只需要最近 10 个字符，也就是 20 位，所以要用掩码截断：

mask &= (1 << 20) - 1

记忆钩子：左移是窗口向右滑，低位塞新字符，高位用掩码裁掉。

三、为什么第 10 个字符后才开始统计

长度不足 10 时，mask 还不是一个完整 DNA 片段。只有当下标 i >= 9 时，最近 10 个字符才构成一个有效窗口。

i = 0..8  => 不足 10 个字符
i = 9     => 第一个长度 10 子串

从这个时刻开始，当前 mask 和 s[i-9..i] 一一对应。

四、如何判断重复

使用两个集合：

seen：已经出现过一次的编码
added：已经加入答案的重复编码

如果当前 mask 不在 seen，加入 seen；如果已经在 seen 且不在 added，说明这是第二次出现，把对应子串加入答案，同时加入 added 防止答案重复。

这样不会因为某个片段出现 3 次而把答案加 2 次。

五、代码模板

List<String> findRepeatedDnaSequences(String s) {
    Map<Character, Integer> map = Map.of('A', 0, 'C', 1, 'G', 2, 'T', 3);
    Set<Integer> seen = new HashSet<>();
    Set<Integer> added = new HashSet<>();
    List<String> ans = new ArrayList<>();
    int mask = 0;
    int keep = (1 << 20) - 1;
    for (int i = 0; i < s.length(); i++) {
        mask = ((mask << 2) | map.get(s.charAt(i))) & keep;
        if (i >= 9) {
            if (!seen.add(mask) && added.add(mask)) {
                ans.add(s.substring(i - 9, i + 1));
            }
        }
    }
    return ans;
}

这里 substring(i-9, i+1) 正好取最近 10 个字符。

六、用小例子理解窗口

假设读到序列 "ACGTACGTAA"：

A C G T A C G T A A
00 01 10 11 00 01 10 11 00 00

这 10 个字符压成 20 位。下一步再读一个 C，左移 2 位后，最早的 A 被高位裁掉，低位加入 C。

这就是字符串滑动窗口在 bit 层面的表现。

七、常见误区与追问

误区：用 4 位编码一个字符。 4 种字符只需要 2 位，4 位会浪费且掩码长度错。
误区：忘记保留低 20 位。 不截断会把更早字符也混进编码。
误区：重复出现多次就多次加入答案。 需要额外集合避免答案重复。
追问：为什么 1<<20 安全？ 20 位远小于 int 31 位有效正数范围。
追问：不用位编码可以吗？ 可以直接用字符串 Set，但会多一些 substring 和哈希成本。
追问：窗口长度变成 L 怎么办？ 保留 2*L 位，掩码是 (1 << (2*L)) - 1，注意溢出。

八、加强记忆

重复 DNA 序列的关键是“四个字符两位够”。每次左移 2 位放入新字符，再用低 20 位掩码保留最近 10 个字符。seen 判断是否出现过，added 防止重复加入答案。它本质是滑动窗口，只是窗口内容用整数压缩了。

简化版

详细版