统计不同回文子序列个数（Count Different Palindromic Subsequences）
字数 4623 2025-12-19 02:33:12

统计不同回文子序列个数（Count Different Palindromic Subsequences）

题目描述

给定一个字符串 s（长度 ≤ 1000，仅包含小写英文字母 'a' 到 'd'），要求统计字符串中 不同的非空回文子序列 的个数。
结果需要对 \(10^9 + 7\) 取模。

示例：

  • 输入：s = "bccb"
    输出：6
    解释：不同的回文子序列有 "b", "c", "bb", "cc", "bcb", "bccb"。
  • 输入：s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
    输出：104860361（取自 LeetCode 730 题）

注意：
“不同”指序列内容不同，即使位置不同但只要字符相同、顺序相同，就算同一个子序列。
例如 "aa" 在字符串 "aaa" 中，子序列可以通过选不同位置的 'a' 得到，但结果 "aa" 只被统计一次。

解题思路

此题的关键是既要判断回文，又要避免重复统计。
直接枚举所有子序列会超时（\(2^n\)），因此采用 动态规划，并利用字符集很小（仅 4 种字符）的特性。

定义状态：
设 dp[i][j] 表示在子串 s[i..j]（包含两端）中，不同的回文子序列 的个数。

状态转移的难点：
如果直接像最长回文子序列那样枚举 s[i] == s[j] 与不等的情况，会导致重复计数。
比如 s = "aba"，子序列 "a" 会从不同位置被多次计入。

正确方法——按两端字符分类计数：
我们可以将 dp[i][j] 再细分为四类（对应 'a' ~ 'd'），但更巧妙的是利用 两端相同字符的位置 来推导。

详细推导

令 dp[i][j] 表示子串 s[i..j] 中不同回文子序列个数。

1. 基本情况：

  • 当 i > j，空串，dp = 0。
  • 当 i == j，只有一个字符，dp[i][j] = 1（就是该字符本身）。

2. 当 s[i] != s[j]：
此时，s[i] 和 s[j] 不能同时作为回文子序列的两端。
我们有：

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

（原理：所有回文子序列要么在 s[i+1..j] 中，要么在 s[i..j-1] 中，但两者交集 s[i+1..j-1] 被重复计算了一次，因此减去。）

3. 当 s[i] == s[j]：
设字符 c = s[i]。
此时所有回文子序列可以分为两类：

  • 不含 c 作为两端：即全部在 s[i+1..j-1] 中，数量为 dp[i+1][j-1]。

  • 含 c 作为两端：可以形成新的回文子序列 c ... c，中间部分来自 s[i+1..j-1] 中的任意回文子序列（可以为空）。
    但要注意，如果 s[i+1..j-1] 中已经有多个 c，直接加 dp[i+1][j-1] 会导致重复？
    其实不会，因为我们要统计的是 不同的回文子序列，即使中间部分相同，加上两端 c 后也是新的不同序列。
    但需要避免重复统计：比如 s = "aba"，i=0, j=2，s[i]='a', s[j]='a'，中间 "b" 是回文子序列，加上两端得 "aba"，而中间空串加上两端得 "aa"，这些都是不同的。

    所以含 c 作为两端的回文子序列数量 = dp[i+1][j-1] + 1（加 1 是因为可以只取两端两个 c，中间为空，即 "cc" 这种，但注意如果中间没有其他字符，"c" 已经算过了吗？
    实际上，"c" 已经在 dp[i+1][j-1] 中？不一定，因为 dp[i+1][j-1] 统计的是 s[i+1..j-1] 中的回文子序列，不包括单个 c 吗？若 i+1 > j-1，则 dp[i+1][j-1]=0，此时我们需要额外加 1（表示 "cc"）以及 "c" 吗？
    仔细分析：
    当 s[i] == s[j] 时，新增加的回文子序列是：

    • 单个字符 c（如果之前没有？其实 dp[i][j-1] 或 dp[i+1][j] 已经包含单个 c，所以新增的是两端 c 构成的长度 ≥2 的回文子序列）
    • 两端为 c，中间为 s[i+1..j-1] 中的任一不同回文子序列（包括空）

    更准确公式（经推导验证）：

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

当 s[i] == s[j] 时？不对，这样会重复加。
标准正确推导（参考 LeetCode 730 官方解法）：

定义 next[i][ch] 表示在位置 i 右侧（包括 i）下一个字符 ch 的位置；
定义 prev[j][ch] 表示在位置 j 左侧（包括 j）上一个字符 ch 的位置。
但更简洁的方法是：

设 L 为 i 右边第一个与 s[i] 相同字符的位置（> i），R 为 j 左边第一个与 s[j] 相同字符的位置（< j）。
当 s[i] == s[j] 时：

  • 如果 L > R，说明 i 和 j 之间没有和两端相同的字符，则新增的回文子序列是：
    dp[i][j] = dp[i+1][j-1] * 2 + 2
    解释：dp[i+1][j-1] 中的每个回文子序列都可以在两端加 c 构成新序列（*2），再加 "c" 和 "cc" 两个新序列（+2）。
  • 如果 L == R，说明中间只有一个相同字符，则新增的序列是：
    dp[i][j] = dp[i+1][j-1] * 2 + 1
    解释：*2 同上，但 "c" 已经在 dp[i+1][j-1] 中（就是中间那个字符），所以只额外加 "cc"（+1）。
  • 如果 L < R，说明中间至少有两个相同字符，则：
    dp[i][j] = dp[i+1][j-1] * 2 - dp[L+1][R-1]
    解释：*2 后要减去重复计算的中间部分（即 s[L+1..R-1] 中的回文子序列加两端后与之前的重复）。

这个方法是避免重复统计的核心。

算法步骤

  1. 预处理数组 next 和 prev（或直接用到时搜索，因为字符集只有 4 种）。
  2. 初始化 dp[i][i] = 1。
  3. 按长度从 2 到 n 遍历：
    • 对每个 i, j：
      • 若 s[i] != s[j]：

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

 - 若 `s[i] == s[j]`：
   令 `c = s[i]`，找 `L` = `i` 右边第一个 `c` 的位置（`> i`），`R` = `j` 左边第一个 `c` 的位置（`< j`）：
     - 如果 `L` 不存在（即没有），则 `L = -1`，但这里用 `L > R` 判断更方便：实际上若 `i` 和 `j` 之间没有相同字符，则 `L > R` 为真（`L` 可能不存在，视为 `n`，`R` 可能不存在，视为 `-1`）。
   具体：
     - 若 `L > R`：`dp[i][j] = dp[i+1][j-1] * 2 + 2`
     - 若 `L == R`：`dp[i][j] = dp[i+1][j-1] * 2 + 1`
     - 若 `L < R`：`dp[i][j] = dp[i+1][j-1] * 2 - dp[L+1][R-1]`
 - 所有运算对 `MOD = 10^9+7` 取模，注意减法可能负数，要加 MOD 再取模。
  1. 最终答案 dp[0][n-1]。

示例演示

以 s = "bccb" 为例：

  1. 初始化：dp[0][0]=1 ("b"), dp[1][1]=1 ("c"), dp[2][2]=1 ("c"), dp[3][3]=1 ("b")。
  2. 长度 2：
    • i=0,j=1："bc", s[i]!=s[j]
      dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2（"b", "c"）
    • i=1,j=2："cc", s[1]==s[2]，找 L,R：
      字符 'c'，L=1 右边第一个 'c' 是 2，R=2 左边第一个 'c' 是 1，所以 L > R？L=2, R=1 是 L > R 吗？错，这里 i=1, j=2，要找的是 i 右边第一个（>1）是 2，j 左边第一个（<2）是 1，所以 L=2, R=1，L > R 成立。
      中间 i+1..j-1 为空，dp[2][1]=0。
      则 dp[1][2] = 0*2 + 2 = 2（"c", "cc"）
    • i=2,j=3："cb", 不同，dp[2][3] = dp[3][3] + dp[2][2] - dp[3][2] = 1 + 1 - 0 = 2（"c", "b"）
  3. 长度 3：
    • i=0,j=2："bcc", s[0]!=s[2]（'b'!='c'），
      dp[0][2] = dp[1][2] + dp[0][1] - dp[1][1] = 2 + 2 - 1 = 3（"b", "c", "cc"）
    • i=1,j=3："ccb", s[1]!=s[3]（'c'!='b'），
      dp[1][3] = dp[2][3] + dp[1][2] - dp[2][2] = 2 + 2 - 1 = 3（"c", "b", "cc"）
  4. 长度 4：
    • i=0,j=3："bccb", s[0]==s[3]=='b'，找 L,R：
      L=0 右边第一个 'b' 是 3，R=3 左边第一个 'b' 是 0，L=3, R=0，L > R？不，L > R 是 3 > 0，成立（中间没有 'b'）。
      中间 i+1..j-1 = "cc"，其 dp[1][2] = 2。
      则 dp[0][3] = 2*2 + 2 = 6。

最终结果 6，与示例一致。

复杂度分析

  • 时间复杂度：\(O(n^2)\)，因为要遍历所有 (i, j)，每次查找 L, R 可以预处理为 O(1)。
  • 空间复杂度：\(O(n^2)\) 存储 dp 数组。

关键点总结

  1. 此题的难点在于 去重，不能简单套用最长回文子序列的转移。
  2. 利用字符集很小的特点，通过寻找相同字符的最近位置来分类讨论，避免重复计数。
  3. 注意取模运算与负数处理。
统计不同回文子序列个数（Count Different Palindromic Subsequences） 题目描述 给定一个字符串 s （长度 ≤ 1000，仅包含小写英文字母 'a' 到 'd' ），要求统计字符串中 不同的非空回文子序列 的个数。 结果需要对 \(10^9 + 7\) 取模。 示例： 输入： s = "bccb" 输出： 6 解释：不同的回文子序列有 "b" , "c" , "bb" , "cc" , "bcb" , "bccb" 。 输入： s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba" 输出： 104860361 （取自 LeetCode 730 题） 注意： “不同”指序列内容不同，即使位置不同但只要字符相同、顺序相同，就算同一个子序列。 例如 "aa" 在字符串 "aaa" 中，子序列可以通过选不同位置的 'a' 得到，但结果 "aa" 只被统计一次。 解题思路 此题的关键是既要判断回文，又要避免重复统计。 直接枚举所有子序列会超时（\(2^n\)），因此采用 动态规划 ，并利用字符集很小（仅 4 种字符）的特性。 定义状态： 设 dp[i][j] 表示在子串 s[i..j] （包含两端）中， 不同的回文子序列 的个数。 状态转移的难点： 如果直接像最长回文子序列那样枚举 s[i] == s[j] 与不等的情况，会导致重复计数。 比如 s = "aba" ，子序列 "a" 会从不同位置被多次计入。 正确方法——按两端字符分类计数： 我们可以将 dp[i][j] 再细分为四类（对应 'a' ~ 'd' ），但更巧妙的是利用 两端相同字符的位置 来推导。 详细推导 令 dp[i][j] 表示子串 s[i..j] 中不同回文子序列个数。 1. 基本情况： 当 i > j ，空串， dp = 0 。 当 i == j ，只有一个字符， dp[i][j] = 1 （就是该字符本身）。 2. 当 s[i] != s[j] ： 此时， s[i] 和 s[j] 不能同时作为回文子序列的两端。 我们有： \[ dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] \] （原理：所有回文子序列要么在 s[i+1..j] 中，要么在 s[i..j-1] 中，但两者交集 s[i+1..j-1] 被重复计算了一次，因此减去。） 3. 当 s[i] == s[j] ： 设字符 c = s[i] 。 此时所有回文子序列可以分为两类： 不含 c 作为两端 ：即全部在 s[i+1..j-1] 中，数量为 dp[i+1][j-1] 。 含 c 作为两端 ：可以形成新的回文子序列 c ... c ，中间部分来自 s[i+1..j-1] 中的任意回文子序列（可以为空）。 但要注意，如果 s[i+1..j-1] 中已经有多个 c ，直接加 dp[i+1][j-1] 会导致重复？ 其实不会，因为我们要统计的是 不同的回文子序列 ，即使中间部分相同，加上两端 c 后也是新的不同序列。 但需要避免重复统计：比如 s = "aba" ， i=0, j=2 ， s[i]='a', s[j]='a' ，中间 "b" 是回文子序列，加上两端得 "aba" ，而中间空串加上两端得 "aa" ，这些都是不同的。 所以含 c 作为两端的回文子序列数量 = dp[i+1][j-1] + 1 （加 1 是因为可以只取两端两个 c ，中间为空，即 "cc" 这种，但注意如果中间没有其他字符， "c" 已经算过了吗？ 实际上， "c" 已经在 dp[i+1][j-1] 中？不一定，因为 dp[i+1][j-1] 统计的是 s[i+1..j-1] 中的回文子序列，不包括单个 c 吗？若 i+1 > j-1 ，则 dp[i+1][j-1]=0 ，此时我们需要额外加 1（表示 "cc" ）以及 "c" 吗？ 仔细分析： 当 s[i] == s[j] 时，新增加的回文子序列是： 单个字符 c （如果之前没有？其实 dp[i][j-1] 或 dp[i+1][j] 已经包含单个 c ，所以新增的是两端 c 构成的长度 ≥2 的回文子序列） 两端为 c ，中间为 s[i+1..j-1] 中的任一不同回文子序列（包括空） 更准确公式（经推导验证）： \[ dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 \] 当 s[i] == s[j] 时？不对，这样会重复加。 标准正确推导（参考 LeetCode 730 官方解法）： 定义 next[i][ch] 表示在位置 i 右侧（包括 i ）下一个字符 ch 的位置； 定义 prev[j][ch] 表示在位置 j 左侧（包括 j ）上一个字符 ch 的位置。 但更简洁的方法是： 设 L 为 i 右边第一个与 s[i] 相同字符的位置（ > i ）， R 为 j 左边第一个与 s[j] 相同字符的位置（ < j ）。 当 s[i] == s[j] 时： 如果 L > R ，说明 i 和 j 之间没有和两端相同的字符，则新增的回文子序列是： dp[i][j] = dp[i+1][j-1] * 2 + 2 解释： dp[i+1][j-1] 中的每个回文子序列都可以在两端加 c 构成新序列（ *2 ），再加 "c" 和 "cc" 两个新序列（ +2 ）。 如果 L == R ，说明中间只有一个相同字符，则新增的序列是： dp[i][j] = dp[i+1][j-1] * 2 + 1 解释： *2 同上，但 "c" 已经在 dp[i+1][j-1] 中（就是中间那个字符），所以只额外加 "cc" （ +1 ）。 如果 L < R ，说明中间至少有两个相同字符，则： dp[i][j] = dp[i+1][j-1] * 2 - dp[L+1][R-1] 解释： *2 后要减去重复计算的中间部分（即 s[L+1..R-1] 中的回文子序列加两端后与之前的重复）。 这个方法是避免重复统计的核心。 算法步骤 预处理数组 next 和 prev （或直接用到时搜索，因为字符集只有 4 种）。 初始化 dp[i][i] = 1 。 按长度从 2 到 n 遍历： 对每个 i, j ： 若 s[i] != s[j] ： \[ dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] \] 若 s[i] == s[j] ： 令 c = s[i] ，找 L = i 右边第一个 c 的位置（ > i ）， R = j 左边第一个 c 的位置（ < j ）： 如果 L 不存在（即没有），则 L = -1 ，但这里用 L > R 判断更方便：实际上若 i 和 j 之间没有相同字符，则 L > R 为真（ L 可能不存在，视为 n ， R 可能不存在，视为 -1 ）。 具体： 若 L > R ： dp[i][j] = dp[i+1][j-1] * 2 + 2 若 L == R ： dp[i][j] = dp[i+1][j-1] * 2 + 1 若 L < R ： dp[i][j] = dp[i+1][j-1] * 2 - dp[L+1][R-1] 所有运算对 MOD = 10^9+7 取模，注意减法可能负数，要加 MOD 再取模。 最终答案 dp[0][n-1] 。 示例演示 以 s = "bccb" 为例： 初始化： dp[0][0]=1 ( "b" ), dp[1][1]=1 ( "c" ), dp[2][2]=1 ( "c" ), dp[3][3]=1 ( "b" )。 长度 2： i=0,j=1 ： "bc" , s[i]!=s[j] dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2 （ "b" , "c" ） i=1,j=2 ： "cc" , s[1]==s[2] ，找 L,R： 字符 'c' ，L=1 右边第一个 'c' 是 2，R=2 左边第一个 'c' 是 1，所以 L > R ？ L=2, R=1 是 L > R 吗？错，这里 i=1, j=2 ，要找的是 i 右边第一个（>1）是 2， j 左边第一个（<2）是 1，所以 L=2, R=1 ， L > R 成立。 中间 i+1..j-1 为空， dp[2][1]=0 。 则 dp[1][2] = 0*2 + 2 = 2 （ "c" , "cc" ） i=2,j=3 ： "cb" , 不同， dp[2][3] = dp[3][3] + dp[2][2] - dp[3][2] = 1 + 1 - 0 = 2 （ "c" , "b" ） 长度 3： i=0,j=2 ： "bcc" , s[0]!=s[2] （ 'b'!='c' ）， dp[0][2] = dp[1][2] + dp[0][1] - dp[1][1] = 2 + 2 - 1 = 3 （ "b" , "c" , "cc" ） i=1,j=3 ： "ccb" , s[1]!=s[3] （ 'c'!='b' ）， dp[1][3] = dp[2][3] + dp[1][2] - dp[2][2] = 2 + 2 - 1 = 3 （ "c" , "b" , "cc" ） 长度 4： i=0,j=3 ： "bccb" , s[0]==s[3]=='b' ，找 L,R： L=0 右边第一个 'b' 是 3，R=3 左边第一个 'b' 是 0，L=3, R=0， L > R ？不， L > R 是 3 > 0 ，成立（中间没有 'b' ）。 中间 i+1..j-1 = "cc" ，其 dp[1][2] = 2 。 则 dp[0][3] = 2*2 + 2 = 6 。 最终结果 6 ，与示例一致。 复杂度分析 时间复杂度：\(O(n^2)\)，因为要遍历所有 (i, j) ，每次查找 L, R 可以预处理为 O(1) 。 空间复杂度：\(O(n^2)\) 存储 dp 数组。 关键点总结 此题的难点在于 去重 ，不能简单套用最长回文子序列的转移。 利用字符集很小的特点，通过寻找相同字符的最近位置来分类讨论，避免重复计数。 注意取模运算与负数处理。