最长公共子序列的变种：带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现） 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符集合 C （例如 C = {'a', 'b'} ）。要求找到 s1 和 s2 的最长公共子序列（LCS），但满足以下附加条件： 子序列中，属于集合 C 的字符必须连续出现（即不能中断）。 非 C 中的字符在子序列中可以任意出现，不受连续性的限制。 例如： s1 = "abcde" , s2 = "ace" , C = {'c'} ，则满足条件的 LCS 是 "ace" （因为 'c' 单独出现视为连续）。 s1 = "aabcde" , s2 = "acde" , C = {'a','b'} ，则满足条件的 LCS 是 "ab" （ 'a' 和 'b' 必须连续，但 s2 中 'a' 和 'c' 之间插入了 'b' ，无法连续匹配 'a' 和 'b' ）。 解题过程 步骤 1：问题分析 标准 LCS 使用动态规划，定义 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度。 本题的约束是： 某些字符必须连续出现 。这意味着在匹配过程中，一旦开始匹配一个 C 中的字符，后续的 C 字符必须连续匹配，不能跳过。 需要扩展状态，记录当前是否处于一个“连续 C 字符段”中。 步骤 2：状态设计 定义 dp[i][j][k] ，其中： i ：匹配到 s1 的第 i 个字符（1-indexed）。 j ：匹配到 s2 的第 j 个字符。 k ：表示当前匹配状态： k = 0 ：当前不在 C 字符的连续段中。 k = 1 ：当前正在 C 字符的连续段中。 步骤 3：状态转移方程 考虑 s1[i-1] 和 s2[j-1] 的匹配情况： 字符相等 （ s1[i-1] == s2[j-1] ）： 若当前字符属于 C ： 如果 k=0 （之前不在连续段），可以开始新连续段： dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][0] + 1) 。 如果 k=1 （已在连续段），必须继续连续段： dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][1] + 1) 。 若当前字符不属于 C ： 无论 k=0 或 k=1 ，都可以匹配： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1) 。 字符不相等 ： 跳过 s1[i-1] ： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) 。 跳过 s2[j-1] ： dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]) 。 注意：如果 k=1 且跳过导致连续段中断，需要特殊处理？实际上，跳过不会影响连续段状态，因为连续段由已匹配的字符决定。 步骤 4：初始化 dp[0][j][0] = 0 ， dp[i][0][0] = 0 （空字符串匹配长度为 0）。 dp[0][j][1] = -inf ， dp[i][0][1] = -inf （不可能在空字符串中处于连续段）。 步骤 5：最终答案 答案为 max(dp[len(s1)][len(s2)][0], dp[len(s1)][len(s2)][1]) 。 举例验证 以 s1 = "aabc" , s2 = "ac" , C = {'a','b'} 为例： 匹配 'a' （属于 C ）时，开始连续段。 接下来 s1 的 'b' 必须连续匹配，但 s2 下一个是 'c' ，无法匹配 'b' ，因此连续段终止。 最终 LCS 为 "a" 或 "ac" ？需检查： "ac" 中 'a' 和 'c' 不连续（ 'a' 属于 C 但 'c' 不属于 C ），所以 'a' 是单独连续段，合法。 但 "ab" 不可能，因为 s2 没有 'b' 。 正确结果是 "ac" 长度 2。 通过以上步骤，我们可以系统地解决带连续字符限制的 LCS 问题。