最长公共子序列的变种——带字符必须按顺序出现限制的最长公共子序列（进阶版：限制某些字符必须连续出现k次） 问题描述 给定两个字符串s和t，以及一个字符集合C和整数k。要求找到s和t的最长公共子序列，且满足： 子序列必须包含集合C中的所有字符（按在C中的顺序出现） 集合C中的每个字符在子序列中必须连续出现恰好k次 例如： s = "abcde", t = "ace", C = "c", k = 1 满足条件的最长公共子序列是"ace"（包含c且c连续出现1次） 解题过程 步骤1：理解问题核心 这是一个带限制条件的最长公共子序列(LCS)问题。我们需要在标准LCS的基础上添加两个约束： 必须包含特定字符（按顺序） 这些字符必须连续出现k次 步骤2：定义状态 定义四维DP数组： dp[i][j][x][y] 表示考虑s的前i个字符、t的前j个字符时： 当前正在处理C中的第x个字符（0 ≤ x ≤ |C|） 当前字符C[ x-1 ]已经连续出现了y次（0 ≤ y ≤ k） 步骤3：状态转移方程 情况1：两个字符串当前字符相同 如果s[ i-1] == t[ j-1 ]： 如果当前字符等于C[ x-1 ]且y > 0： 继续累积： dp[i][j][x][y] = dp[i-1][j-1][x][y-1] + 1 如果当前字符等于C[ x-1 ]且y == 0： 开始新的连续段： dp[i][j][x][1] = dp[i-1][j-1][x-1][k] + 1 如果当前字符不等于C[ x-1 ]： 普通匹配： dp[i][j][x][0] = dp[i-1][j-1][x][0] + 1 情况2：两个字符串当前字符不同 跳过s的当前字符： dp[i][j][x][y] = dp[i-1][j][x][y] 跳过t的当前字符： dp[i][j][x][y] = dp[i][j-1][x][y] 步骤4：初始化 dp[0][j][0][0] = 0 （s为空串） dp[i][0][0][0] = 0 （t为空串） 其他情况初始化为负无穷（表示不可达状态） 步骤5：最终答案 答案是所有 dp[m][n][|C|][k] 中的最大值，其中m和n分别是s和t的长度。 举例说明 假设s = "aabbcc", t = "abcabc", C = "bc", k = 2 处理过程： 匹配"a"：普通字符，不影响C序列 匹配第一个"b"：开始C序列的第一个字符，y=1 匹配第二个"b"：继续累积，y=2（满足k=2要求） 匹配第一个"c"：切换到C序列的第二个字符，y=1 匹配第二个"c"：继续累积，y=2（满足所有条件） 最终得到满足条件的LCS："abbcc" 复杂度分析 时间复杂度：O(m × n × |C| × k) 空间复杂度：O(m × n × |C| × k) 这个算法通过四维DP精确地跟踪了字符匹配、C序列进度和连续出现次数三个维度的信息，确保了所有条件都能被满足。