线性动态规划：最长公共子序列的变种——带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现）

字数 2237 2025-11-02 10:11:13

线性动态规划：最长公共子序列的变种——带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现）

题目描述
给定两个字符串 s 和 t，以及一个字符集合 C（例如 C = {'a', 'b'}），要求找到 s 和 t 的最长公共子序列（LCS），且该子序列必须满足：对于集合 C 中的每个字符，如果它在子序列中出现，则必须连续出现至少 k 次（例如 k=2）。如果无法满足条件，返回 0。

示例

输入：s = "aababc", t = "aabdbc", C = {'a'}, k = 2
解释：普通 LCS 可能是 "aabab"（长度 5），但 'a' 在子序列中未连续出现至少 2 次（例如 "aabab" 中 'a' 被 'b' 隔断）。满足条件的 LCS 是 "aaba"（'a' 连续出现 2 次以上），但需验证在 t 中的匹配情况。实际最长可行子序列是 "aab"（'a' 连续出现 2 次）。

解题思路

状态定义
设 dp[i][j][x] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，当前已匹配的子序列末尾连续字符为 x（x 属于 C 或特殊标记 0 表示非 C 字符），且连续出现次数的状态。但直接记录连续次数会导致状态爆炸，需优化。
- 简化：将问题拆分为两种模式：
  - 模式 A：当前子序列末尾是 C 中的字符，且正在累计连续次数。
  - 模式 B：当前子序列末尾是非 C 字符或 C 字符但未累计连续次数。
状态转移
- 定义 dp[i][j][c][cnt] 为考虑 s[0..i-1] 和 t[0..j-1]，当前子序列末尾字符为 c（c 属于 C 或空标记），且 c 已连续出现 cnt 次时的最长长度。
- 初始状态：dp[0][j][*][*] = 0，dp[i][0][*][*] = 0。
- 转移方程：
  1. 不选 s[i-1] 或 t[j-1]：
    dp[i][j][c][cnt] = max(dp[i-1][j][c][cnt], dp[i][j-1][c][cnt])
  2. 当 s[i-1] == t[j-1] 时，设字符 ch = s[i-1]：
    - 若 ch 不属于 C：可直接追加，重置状态为 ch 出现 1 次（或非 C 模式）。
    - 若 ch 属于 C：
      - 若前状态字符也是 ch，则连续次数 cnt 增加 1，但需保证 cnt ≤ k？
      - 若前状态字符不是 ch，则需检查是否满足 k 次连续的条件后才能切换字符。
连续字符约束处理
- 关键：只有当 ch 属于 C 且连续出现次数 cnt >= k 时，才允许在子序列中切换到其他字符。
- 实现时，可用辅助状态 free 表示当前无连续字符约束（即末尾是非 C 字符，或 C 字符已满足 k 次连续）。
优化状态设计
- 将状态简化为 dp[i][j][lastChar][continuousCount]，其中 lastChar 为当前末尾字符（用索引表示），continuousCount 记录连续次数。
- 初始化：dp[0][0][0][0] = 0（lastChar=0 表示无字符）。
- 转移：
  - 忽略 s[i] 或 t[j]：继承状态。
  - 匹配 s[i] 和 t[j]：
    - 如果 s[i] 不属于 C，则可直接追加，重置连续次数为 1。
    - 如果 s[i] 属于 C：
      - 若前状态字符也是 s[i]，则连续次数 +1。
      - 若前状态字符不是 s[i]，则必须前状态字符为非 C 或已满足 k 次连续，才能切换。
最终答案
- 遍历所有 i, j，以及所有可能的 lastChar 和 continuousCount，取最大值，且需保证当前状态满足约束（若 lastChar 属于 C，则 continuousCount >= k 或为 0）。

详细步骤

初始化 DP 表，尺寸 [len(s)+1][len(t)+1][|C|+2][k+1]（多出的两个状态用于非 C 字符和空字符）。
遍历 i 从 0 到 len(s)，j 从 0 到 len(t)：
- 对于每个状态 (lastChar, cnt)：
  - 继承不选当前字符的状态。
  - 若 s[i-1] == t[j-1]：
    - 计算新连续次数：若字符匹配且与前状态字符相同，则 newCnt = cnt + 1，否则 newCnt = 1。
    - 检查约束：若新字符属于 C 且 newCnt < k，则只能更新当前字符的状态，不能切换到其他字符。
    - 更新 DP 值。
答案取所有满足约束的状态的最大值。

复杂度分析

时间复杂度：O(n * m * |C| * k)，其中 n 和 m 为字符串长度。
空间复杂度：可通过滚动数组优化到 O(m * |C| * k)。

关键点

通过状态 (lastChar, continuousCount) 刻画连续字符约束。
在状态转移时，严格检查是否允许切换字符。
初始化需注意空状态的边界处理。

线性动态规划：最长公共子序列的变种——带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现）题目描述给定两个字符串 s 和 t ，以及一个字符集合 C （例如 C = {'a', 'b'} ），要求找到 s 和 t 的最长公共子序列（LCS），且该子序列必须满足：对于集合 C 中的每个字符，如果它在子序列中出现，则必须连续出现至少 k 次（例如 k=2 ）。如果无法满足条件，返回 0。示例输入： s = "aababc", t = "aabdbc", C = {'a'}, k = 2 解释：普通 LCS 可能是 "aabab" （长度 5），但 'a' 在子序列中未连续出现至少 2 次（例如 "aabab" 中 'a' 被 'b' 隔断）。满足条件的 LCS 是 "aaba" （ 'a' 连续出现 2 次以上），但需验证在 t 中的匹配情况。实际最长可行子序列是 "aab" （ 'a' 连续出现 2 次）。解题思路状态定义设 dp[i][j][x] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时，当前已匹配的子序列末尾连续字符为 x （ x 属于 C 或特殊标记 0 表示非 C 字符），且连续出现次数的状态。但直接记录连续次数会导致状态爆炸，需优化。简化：将问题拆分为两种模式：模式 A ：当前子序列末尾是 C 中的字符，且正在累计连续次数。模式 B ：当前子序列末尾是非 C 字符或 C 字符但未累计连续次数。状态转移定义 dp[i][j][c][cnt] 为考虑 s[0..i-1] 和 t[0..j-1] ，当前子序列末尾字符为 c （ c 属于 C 或空标记），且 c 已连续出现 cnt 次时的最长长度。初始状态： dp[0][j][*][*] = 0 ， dp[i][0][*][*] = 0 。转移方程：不选 s[i-1] 或 t[j-1] ： dp[i][j][c][cnt] = max(dp[i-1][j][c][cnt], dp[i][j-1][c][cnt]) 当 s[i-1] == t[j-1] 时，设字符 ch = s[i-1] ：若 ch 不属于 C ：可直接追加，重置状态为 ch 出现 1 次（或非 C 模式）。若 ch 属于 C ：若前状态字符也是 ch ，则连续次数 cnt 增加 1，但需保证 cnt ≤ k ？若前状态字符不是 ch ，则需检查是否满足 k 次连续的条件后才能切换字符。连续字符约束处理关键：只有当 ch 属于 C 且连续出现次数 cnt >= k 时，才允许在子序列中切换到其他字符。实现时，可用辅助状态 free 表示当前无连续字符约束（即末尾是非 C 字符，或 C 字符已满足 k 次连续）。优化状态设计将状态简化为 dp[i][j][lastChar][continuousCount] ，其中 lastChar 为当前末尾字符（用索引表示）， continuousCount 记录连续次数。初始化： dp[0][0][0][0] = 0 （ lastChar=0 表示无字符）。转移：忽略 s[i] 或 t[j] ：继承状态。匹配 s[i] 和 t[j] ：如果 s[i] 不属于 C ，则可直接追加，重置连续次数为 1。如果 s[i] 属于 C ：若前状态字符也是 s[i] ，则连续次数 +1。若前状态字符不是 s[i] ，则必须前状态字符为非 C 或已满足 k 次连续，才能切换。最终答案遍历所有 i , j ，以及所有可能的 lastChar 和 continuousCount ，取最大值，且需保证当前状态满足约束（若 lastChar 属于 C ，则 continuousCount >= k 或为 0）。详细步骤初始化 DP 表，尺寸 [len(s)+1][len(t)+1][|C|+2][k+1] （多出的两个状态用于非 C 字符和空字符）。遍历 i 从 0 到 len(s) ， j 从 0 到 len(t) ：对于每个状态 (lastChar, cnt) ：继承不选当前字符的状态。若 s[i-1] == t[j-1] ：计算新连续次数：若字符匹配且与前状态字符相同，则 newCnt = cnt + 1 ，否则 newCnt = 1 。检查约束：若新字符属于 C 且 newCnt < k ，则只能更新当前字符的状态，不能切换到其他字符。更新 DP 值。答案取所有满足约束的状态的最大值。复杂度分析时间复杂度： O(n * m * |C| * k) ，其中 n 和 m 为字符串长度。空间复杂度：可通过滚动数组优化到 O(m * |C| * k) 。关键点通过状态 (lastChar, continuousCount) 刻画连续字符约束。在状态转移时，严格检查是否允许切换字符。初始化需注意空状态的边界处理。