LeetCode 730. 统计不同回文子序列

2022-04-06 HGNULB 约 17 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 730. 统计不同回文子序列

题意分析

给定一个字符串 s，统计它有多少个互不相同的非空回文子序列，结果对 $10^9+7$ 取模。子序列是删掉若干字符后剩下的序列，不要求连续；两个子序列只要字符内容相同就算同一个，无论它们在原串里由哪些下标构成。

「不同」这两个字是整道题的分水岭。如果只是统计回文子序列的出现次数，那就是一道模板题：按区间划分，两端相同时把内部答案乘二再加二即可。但一旦要求去重，同一个字符串通过不同下标组合被数了很多遍，朴素的区间转移会严重多算。以 aaa 为例，按下标算有 7 个回文子序列（三个单 a、三个 aa、一个 aaa），按内容去重后只有 3 个。所以本题的全部难度，都集中在「怎样在转移里精确地扣掉重复」。

约束给了两个关键信号。第一，字符集只有 a b c d 四种，这个异常严格的限定几乎是在明说：你被允许对每种字符单独做预处理，$4n$ 的辅助表是免费的。第二，$1 \le s \le 1000$，$n^2$ 的状态数是 $10^6$，转移必须是 $O(1)$。这两条合起来把解法空间压得很窄——必须是区间型的二维状态，且每次转移只能查常数张预处理表。

还有一处约束容易被忽略：取模。中间转移里出现了减法（无论是容斥还是去重扣除），取模后的差值可能为负，必须显式修正回非负区间，否则最终结果会是一个负数或错误的余数。

边界方面：长度为 1 的区间答案恒为 1；空区间答案为 0，而这个 0 会被转移式频繁引用（比如两端相邻时的「内部」就是空区间），所以状态数组的默认零值恰好承担了这个语义，不需要额外初始化。

解法：区间 DP（去重计数）

核心思路

先看暴力：枚举所有 $2^n$ 个子序列，逐个判回文并塞进哈希集合去重。$n$ 到 1000 时这条路彻底不可行，但它明确了目标——我们要的是一个集合的大小，而不是一个计数的累加。瓶颈由此暴露：任何按「选哪些下标」来计数的方法都天生带重复，必须换一种不会产生重复的组织方式。

换的方式是：按字符串内容本身来划分。设 $dp[i][j]$ 表示子串 s[i..j]（闭区间）中互不相同的非空回文子序列的个数。这个状态定义的关键在于它统计的是「不同的字符串」而非「不同的下标组合」，所以转移时必须保证不同来源产生的字符串集合要么不相交，要么被显式做了容斥。

两端字符不同时（s[i] != s[j]）。s[i..j] 里的任何回文子序列，要么不用到下标 i，要么不用到下标 j——不可能同时用到，因为回文的首尾字符必须相等，而这两个位置的字符不同。于是集合 $P(i,j)$ 等于 $P(i+1,j) \cup P(i,j-1)$，两者的交集恰好是 $P(i+1,j-1)$。按容斥原理：

$dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]$

两端字符相同时（s[i] == s[j] == c）。把 $P(i,j)$ 按「是否以 c 开头且以 c 结尾」切成两半。不以 c 为首尾的那些，一定完全落在 s[i+1..j-1] 内部，个数是 $dp[i+1][j-1]$ 减去内部那些以 c 为首尾的。以 c 为首尾的那些，可以写成 c + X + c 的形式（X 是 s[i+1..j-1] 中的任一回文子序列或空串），再加上单字符 c 本身，共 $dp[i+1][j-1] + 2$ 个。

直接把两部分相加会重复计算「内部本来就以 c 为首尾」的那些串，因为它们既属于内部集合，又能被外层包裹的形式生成。所以先写出朴素的 $2 \cdot dp[i+1][j-1] + 2$，再减掉重复量，而重复量取决于 c 在开区间 $(i, j)$ 内出现了几次：

一次都没出现：内部不可能有以 c 开头的串，无重复，$dp[i][j] = 2 \cdot dp[i+1][j-1] + 2$。新增的 2 个就是 c 和 cc。

恰好出现一次（记位置为 $l = r$）：内部以 c 为首尾的串只有单字符 c 一个（凑不出两个 c），重复量为 1，$dp[i][j] = 2 \cdot dp[i+1][j-1] + 1$。

出现两次及以上（首次在 $l$、末次在 $r$，$l < r$）：内部以 c 为首尾的串包括 c、cc，以及所有形如 c + Y + c 的串，其中 Y 是 s[l+1..r-1] 中的回文子序列。这类串的总数是 $dp[l+1][r-1] + 2$。于是 $dp[i][j] = 2 \cdot dp[i+1][j-1] + 2 - (dp[l+1][r-1] + 2) = 2 \cdot dp[i+1][j-1] - dp[l+1][r-1]$。

第三种情况里为什么取的是最靠内的一对 c（首次出现 $l$ 与末次出现 $r$）：因为「内部以 c 为首尾的回文子序列」这个集合，其内容只由最外一对可用的 c 之间的自由部分决定。用 $l$ 和 $r$ 界定，才能不重不漏地刻画 s[l+1..r-1] 这段自由区。若取了中间某一对 c，就会漏掉那些跨度更大的串。

要在 $O(1)$ 时间拿到 $l$ 和 $r$，就得靠字符集只有 4 这个条件：预处理两张表，nextPos[i][c] 记录下标不小于 i 的第一个字符 c 的位置，prevPos[i][c] 记录下标不超过 i 的最后一个字符 c 的位置，各 $4n$ 个格子。查询时 $l = $ nextPos[i+1][c]、$r = $ prevPos[j-1][c]，并用 $l = -1$ 或 $l > r$ 统一表示「区间内没有 c」——这个判断同时覆盖了「整串右侧没有 c」和「有 c 但都在 j-1 之外」两种情形，不需要分开写。

最后是遍历顺序。所有转移都引用比当前区间更短的区间（$[i+1, j]$、$[i, j-1]$、$[i+1, j-1]$、$[l+1, r-1]$ 全部严格更短），所以按区间长度从小到大填表即可保证依赖已就绪。第四个引用 $[l+1, r-1]$ 尤其值得注意：它满足 $i < l+1$ 且 $r-1 < j$，长度确实更小，但它不是前三个的邻接区间，靠「按长度递增」这个顺序才能一并覆盖。

解题步骤

第一步，预处理 prevPos。 正序扫描，维护一个长度为 4 的 last 数组记录每种字符最近一次出现的位置，每到一个下标就先更新 last，再把 last 整体拷进 prevPos[i]。为什么先更新再拷贝：prevPos[i][c] 的定义是「下标不超过 i」，包含 i 自身，所以当前字符必须先记进去。

第二步，预处理 nextPos。 逆序扫描，同样的模式。为什么要单独扫一遍而不是从 prevPos 推导：两张表的方向不同，逆序扫描是唯一能在 $O(n)$ 内得到「不小于 i 的首次出现」的方式。

第三步，初始化 $dp[i][i] = 1$。 为什么是 1：单个字符自身就是一个回文子序列，且只有这一个。其余格子保持 0，其中 $i > j$ 的非法格子的 0 恰好表示「空区间没有回文子序列」，转移式会直接引用这个语义。

第四步，按区间长度 len 从 2 递增到 n，内层枚举左端点 i，右端点 j = i + len - 1。 为什么必须按长度而不是按下标：转移引用的四个区间全部更短，但它们的左端点可能比 i 大、右端点可能比 j 小，只有「长度递增」这一个顺序能保证它们无一例外都已算好。

第五步，两端不同走容斥式。 为什么要减 $dp[i+1][j-1]$：$P(i+1,j)$ 与 $P(i,j-1)$ 都包含了完全落在 s[i+1..j-1] 中的那些串，不减就会把它们数两遍。

第六步，两端相同时先查 $l$、$r$，再按三种情况取式子。 为什么要区分三种而不是统一用第三式：$l$ 不存在或 $l > r$ 时 $dp[l+1][r-1]$ 根本没有意义；$l = r$ 时 $dp[l+1][r-1]$ 是空区间的 0，代入第三式会得到 $2 \cdot dp + 0$，比正确答案 $2 \cdot dp + 1$ 少 1。三个分支互不可替代。

第七步，每个格子算完立刻取模，并在结果为负时加回模数。 为什么必须修正：容斥式和去重式都含减法，两个已取模的数相减可能落到 $(-mod, 0)$ 区间；不修正的话这个负数会一路传播，最终返回负值。

第八步，返回 $dp[0][n-1]$。

以 s = "bccb" 走一遍，下标 0 到 3 分别是 b c c b。

预处理后，prevPos[1][c] = 1（下标 ≤ 1 的最后一个 c 在 1），prevPos[2][b] = 0（下标 ≤ 2 的最后一个 b 在 0），nextPos[1][b] = 3，nextPos[2][c] = 2。初始化 $dp[0][0] = dp[1][1] = dp[2][2] = dp[3][3] = 1$。

长度 2。区间 $[0,1]$ 是 bc，两端不同：$dp = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2$，对应 b 和 c。这里 $dp[1][0]$ 是非法区间，取 0，正是「两个单字符集合不相交」的体现。区间 $[1,2]$ 是 cc，两端相同，$c = $ c：$l = $ nextPos[2][c] $= 2$，$r = $ prevPos[1][c] $= 1$，$l > r$ 说明开区间 $(1,2)$ 内没有 c，走第一式：$dp = 2 \cdot dp[2][1] + 2 = 0 + 2 = 2$，对应 c 和 cc。区间 $[2,3]$ 是 cb，两端不同：$dp = 1 + 1 - 0 = 2$。

长度 3。区间 $[0,2]$ 是 bcc，两端 b 与 c 不同：$dp = dp[1][2] + dp[0][1] - dp[1][1] = 2 + 2 - 1 = 3$，对应 b、c、cc。减掉的 1 正是被两个子区间重复计入的 c。区间 $[1,3]$ 是 ccb，同理得 $2 + 2 - 1 = 3$，对应 c、cc、b。

长度 4。区间 $[0,3]$ 是 bccb，两端都是 b：$l = $ nextPos[1][b] $= 3$，$r = $ prevPos[2][b] $= 0$，$l = 3 > r = 0$，说明开区间 $(0,3)$ 内没有 b，走第一式：$dp = 2 \cdot dp[1][2] + 2 = 2 \cdot 2 + 2 = 6$。

返回 6。逐一列出验证：b、c、bb、cc、bcb、bccb，恰好 6 个。其中 $2 \cdot dp[1][2]$ 的两份分别是「内部 cc 的两个回文 c 和 cc」以及「把它们用 b 包起来得到的 bcb 和 bccb」，额外的 2 是 b 和 bb。

另外两个分支各举一例便于对照。s = "aaa" 求 $dp[0][2]$：两端都是 a，$l = $ nextPos[1][a] $= 1$，$r = $ prevPos[1][a] $= 1$，$l = r$ 走第二式，$dp = 2 \cdot dp[1][1] + 1 = 3$，对应 a、aa、aaa。若误用第一式会得到 4，多出来的一个正是被数了两次的 a。s = "aaaa" 求 $dp[0][3]$：$l = 1$、$r = 2$，$l < r$ 走第三式，$dp = 2 \cdot dp[1][2] - dp[2][1] = 2 \cdot 2 - 0 = 4$，对应 a、aa、aaa、aaaa。

代码实现

class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        int mod = 1_000_000_007;
        char[] a = s.toCharArray();

        int[][] nextPos = new int[n][4];
        int[][] prevPos = new int[n][4];

        int[] last = new int[4];
        Arrays.fill(last, -1);
        for (int i = 0; i < n; i++) {
            int c = a[i] - 'a';
            last[c] = i;
            for (int t = 0; t < 4; t++) {
                prevPos[i][t] = last[t];
            }
        }

        Arrays.fill(last, -1);
        for (int i = n - 1; i >= 0; i--) {
            int c = a[i] - 'a';
            last[c] = i;
            for (int t = 0; t < 4; t++) {
                nextPos[i][t] = last[t];
            }
        }

        long[][] dp = new long[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (a[i] != a[j]) {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                } else {
                    int ch = a[i] - 'a';
                    int l = nextPos[i + 1][ch];
                    int r = prevPos[j - 1][ch];

                    if (l == -1 || l > r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                    }
                }

                dp[i][j] %= mod;
                if (dp[i][j] < 0) {
                    dp[i][j] += mod;
                }
            }
        }

        return (int) dp[0][n - 1];
    }
}

func countPalindromicSubsequences(s string) int {
    const mod int64 = 1_000_000_007
    n := len(s)
    a := []byte(s)

    nextPos := make([][4]int, n)
    prevPos := make([][4]int, n)

    last := [4]int{-1, -1, -1, -1}
    for i := 0; i < n; i++ {
        last[a[i]-'a'] = i
        for t := 0; t < 4; t++ {
            prevPos[i][t] = last[t]
        }
    }

    last = [4]int{-1, -1, -1, -1}
    for i := n - 1; i >= 0; i-- {
        last[a[i]-'a'] = i
        for t := 0; t < 4; t++ {
            nextPos[i][t] = last[t]
        }
    }

    dp := make([][]int64, n)
    for i := range dp {
        dp[i] = make([]int64, n)
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            if a[i] != a[j] {
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            } else {
                ch := a[i] - 'a'
                l := nextPos[i+1][ch]
                r := prevPos[j-1][ch]
                if l == -1 || l > r {
                    dp[i][j] = dp[i+1][j-1]*2 + 2
                } else if l == r {
                    dp[i][j] = dp[i+1][j-1]*2 + 1
                } else {
                    dp[i][j] = dp[i+1][j-1]*2 - dp[l+1][r-1]
                }
            }

            dp[i][j] %= mod
            if dp[i][j] < 0 {
                dp[i][j] += mod
            }
        }
    }

    return int(dp[0][n-1])
}

复杂度分析

时间复杂度：$O(n^2)$。两次预处理各扫一遍字符串、每个位置拷贝 4 个值，是 $O(4n)$；主循环枚举 $O(n^2)$ 个区间，每个区间的转移只做常数次查表与算术，没有任何内层循环。$n \le 1000$ 时约 $10^6$ 次转移，轻松通过。

空间复杂度：$O(n^2)$。$dp$ 表是 $n \times n$ 的 64 位整数数组，占用主导地位；两张位置表各 $4n$，是低阶项。这里不能改成滚动数组，因为转移会引用 $[l+1, r-1]$ 这个与当前行相距任意远的区间，压缩维度就取不到它了。

关键点总结

「计数」与「计数不同的」是两类问题。前者可以随意累加，后者必须保证每个对象只在唯一一个分支里被产生。识别出题目要的是集合大小之后，状态定义就必须以「内容」而非「下标组合」为单位，这一步想不清楚，后面所有公式都无从谈起。

两端相同时的三分支，本质是「内部有多少个同字符可用」。零个、一个、两个及以上分别对应「无重复」「重复一个单字符」「重复一整族串」。这种「按某个关键量的取值分档」的去重思路，在带去重的子序列计数题里反复出现，值得当成模板记住。

容斥是区间 DP 处理「并集」的默认工具。两端不同时 $dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]$ 的形式，和二维前缀和、区间覆盖问题的加减法完全同构。看到「要么不含左端、要么不含右端」的分解，就该条件反射地写出这个式子。

字符集大小是隐藏的复杂度参数。本题若字符集是 26，$4n$ 的表变成 $26n$，依然可行；但若是任意 Unicode，就必须换成按需查找的结构。约束里写死 a 到 d 是出题人给的许可证，看到这种异常具体的限定要立刻意识到「这里允许我按字符枚举」。

含减法的取模一律要做非负修正。这不是本题特有的，而是所有带容斥、带差分的取模计数题的固定收尾动作。写完减法转移后立刻补上修正，比事后调试负数结果高效得多。

面试视角：这题在面试里极少要求当场写完整代码，更常见的是让你讲清楚「去重是怎么做到的」。回答的黄金路径是：先说朴素区间 DP 会重复计数并举 aaa 为例，再说按「是否以两端字符为首尾」切分集合，最后按内部同字符出现次数分三档给出扣除量。能主动指出「$[l+1][r-1]$ 的引用导致无法滚动数组压缩空间」和「取模减法要修正符号」，是把这题讲透的两个加分点。如果面试官改问「字符集变成 26 怎么办」，要能立刻答出预处理表从 $4n$ 变 $26n$、算法结构完全不变。

易错点总结

错误写法：两端相同时统一用 $2 \cdot dp[i+1][j-1] + 2$，不分三档。以 s = "aaa" 为例，会算出 $2 \cdot 1 + 2 = 4$，而正确答案是 3——多出来的那个 a 被数了两遍（一次来自内部集合，一次来自「单字符 c」）。这是本题最核心的错误。

错误写法：$l = r$ 的情况并入第三式，即用 $2 \cdot dp[i+1][j-1] - dp[l+1][r-1]$。以 s = "aaa" 为例，$l = r = 1$，$dp[2][0]$ 是非法区间取 0，结果为 $2 \cdot 1 - 0 = 2$，比正确答案 3 少 1，漏掉了 aa。三个分支的常数项各不相同，不能合并。

错误写法：第三档取的不是最内侧一对同字符，比如用 $l$ 和 $l+1$ 处的两个 c。以 s = "acaca" 为例，求 $dp[0][4]$ 时正确的 $l = 2$、$r = 2$（开区间 $(0,4)$ 内 a 只出现在下标 2），走第二式得 $2 \cdot dp[1][3] + 1$；若错取了别的位置对，扣除量会覆盖错误的自由区，答案偏离。$l$ 必须是首次出现、$r$ 必须是末次出现。

错误写法：两端不同时忘记减 $dp[i+1][j-1]$。以 s = "bcc" 为例，$dp[0][2] = dp[1][2] + dp[0][1] = 2 + 2 = 4$，而正确答案是 3——c 同时出现在两个子区间的答案里被数了两遍。

错误写法：遍历顺序按左端点从 0 递增、右端点从 i 递增。以任意长度不小于 3 的串为例，计算 $dp[0][2]$ 时需要 $dp[1][2]$，但在这种顺序下 $dp[1][2]$ 尚未计算，读到的是 0，整张表从此全错。必须按区间长度递增。

错误写法：取模后不做负数修正。构造一个含大量 a 的长串（例如 900 个 a 加若干 b）时，$2 \cdot dp[i+1][j-1] - dp[l+1][r-1]$ 在两项都已取模的情况下可能得到负值，该负值随转移逐层放大，最终返回一个负数，判题直接判错。

错误写法：dp 用 int 而非 64 位整数。以任意会让 $dp[i+1][j-1]$ 接近 $10^9$ 的输入为例，$dp[i+1][j-1] \times 2$ 达到约 $2 \times 10^9$，超过 32 位有符号上限而溢出成负数，即便之后取模也无法还原，结果错误。

错误写法：预处理 prevPos 时先拷贝 last 再更新。以 s = "cc" 求 $dp[0][1]$ 为例，prevPos[1][c] 会变成 0 而不是 1，$r$ 取错，$l = 2 > r = 0$ 的判断虽然仍走第一式而侥幸不错；但换成 s = "cac"，prevPos[1][c] 应为 0，若顺序反了会变成 -1，l > r 的判断结果改变，走进错误分支。定义里含不含当前下标，决定了更新与拷贝的先后。

错误写法：nextPos 与 prevPos 的查询下标写成 nextPos[i][ch] 和 prevPos[j][ch]。以 s = "cc" 为例，$l = $ nextPos[0][c] $= 0$、$r = $ prevPos[1][c] $= 1$，$l < r$ 走第三式得 $2 \cdot 0 - dp[1][0] = 0$，而正确答案是 2。查询范围必须是开区间 $(i, j)$，所以起点是 i+1、终点是 j-1。

错误写法：判断内部无同字符时只写 l == -1，漏掉 l > r。以 s = "cabc" 求 $dp[0][3]$ 为例（两端都是 c），$l = $ nextPos[1][c] $= 3$，但 3 已经超出了开区间的右界；$r = $ prevPos[2][c] $= 0$，同样在左界之外。若只判 l == -1，这里 $l = 3 \ne -1$ 会走到 $l > r$ 之外的分支，把 $dp[4][-1]$ 读成越界或错值。两个条件必须一起判。

错误写法：为省空间把 dp 压成滚动数组。以 s = "abcba" 为例，计算 $dp[0][4]$ 时第三档会引用 $dp[l+1][r-1]$，其左端点与当前 i 相距不定，滚动后这一行早已被覆盖，读到的是别的区间的值，答案随输入而随机出错。本题的空间无法压缩。

错误写法：把 $dp[i][i] = 1$ 写成 $dp[i][i] = 0$，或忘记初始化。以 s = "ab" 为例，$dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 0 + 0 - 0 = 0$，返回 0 而正确答案是 2。单字符的基准值是整张表的地基。

相似题目

题目	难度	考察点
516. 最长回文子序列	中等	同样的区间 DP 骨架，但求最值不求个数，无需去重，转移只有两分支
647. 回文子串	中等	统计的是连续子串且按位置计数（允许内容重复），中心扩展即可，无需 DP 表
5. 最长回文子串	中等	连续子串求最长，重点在中心扩展或 Manacher，与子序列的区间转移是两套思路
940. 不同的子序列 II	困难	同样是「不同子序列」计数但不要求回文，用线性 DP 按末位字符去重
115. 不同的子序列	困难	数的是匹配目标串的下标组合数，恰恰不去重，是本题的镜像对照
312. 戳气球	困难	区间 DP 的另一经典形态，按「最后戳破谁」划分而非按两端字符关系
132. 分割回文串 II	困难	先预处理回文判定表再做线性 DP 求最少切割，回文只是约束而非计数对象
1143. 最长公共子序列	中等	双串二维 DP，把本题的「区间两端」换成「两串末尾」，是子序列 DP 的入门形态
1147. 段式回文	困难	求最多能切成几段使整体对称，靠双端贪心匹配而非区间 DP