最长公共子序列的变种：带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现k次） 题目描述 给定两个字符串 s1 和 s2 ，以及一个整数 k 。要求找到它们的最长公共子序列（LCS），但附加条件为：在公共子序列中， 某些指定字符必须连续出现至少 k 次 （若出现）。例如，若指定字符为 'a' 且 k=3 ，则公共子序列中若包含 'a' ，则必须连续出现至少 3 次（如 "aaa" 是合法的，但 "aa" 不合法）。需设计动态规划算法求解。 解题思路 此问题在标准 LCS 动态规划基础上，需增加状态维度以跟踪当前字符的连续出现次数。核心步骤包括： 状态定义 设 dp[i][j][c][t] 表示考虑 s1 的前 i 个字符和 s2 的前 j 个字符时，以字符 c 结尾、且 c 已连续出现 t 次的最长公共子序列长度。 c 为当前连续字符（用字母索引或特殊值表示，如 0~25 对应 a~z）。 t 为连续次数（1 ≤ t ≤ k，若 t < k 则当前字符未满足条件；t = k 表示已满足）。 状态转移 若 s1[i] == s2[j] ： 当前字符匹配，需更新以该字符结尾的序列： 若前一状态也是相同字符 c 且连续次数为 t-1 ，则可延续连续序列： dp[i][j][c][t] = max(自身, dp[i-1][j-1][c][t-1] + 1) 若前一状态为其他字符或初始状态，则开始新连续序列（t=1）： dp[i][j][c][1] = max(自身, dp[i-1][j-1][c_prev][t_prev] + 1) ，其中 c_prev 可为任意字符。 若字符不匹配 ： 继承左方或上方的状态： dp[i][j][c][t] = max(dp[i-1][j][c][t], dp[i][j-1][c][t]) 。 初始条件 初始时 dp[0][j][*][*] = 0 ， dp[i][0][*][*] = 0 （空串无公共子序列）。 可设一个特殊状态表示“未开始连续字符”（如 t=0），简化转移。 结果提取 最终答案为所有 dp[n][m][c][t] 的最大值，但需确保： 若字符 c 被指定需满足连续条件，则仅当 t == k 时状态有效； 其他字符无限制（t ≥ 1 即可）。 示例说明 设 s1 = "aabaa" , s2 = "aacaa" ，要求字符 'a' 必须连续出现 k=2 次。 公共子序列包括 "aaa" （ s1 索引 0,1,3,4 选 3 个； s2 类似），但需检查 'a' 的连续段： 子序列 "aaa" 中若三个 'a' 均连续（如索引连续），则合法；若被非 'a' 间隔则非法。 动态规划过程中，当匹配到 'a' 时，需累加连续次数，仅当连续次数达到 2 才纳入有效解。 优化与实现注意 可压缩状态：仅需记录当前连续字符和次数，无需存储完整历史。 若字符集较大，可用哈希表或数组映射字符索引。 时间复杂度 O(n·m·|Σ|·k)，其中 |Σ| 为字符集大小，适用于小 k 和有限字符集。 通过以上步骤，可求解带连续出现次数限制的 LCS 问题。