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

题目描述
给定两个字符串 s 和 t，以及一个字符集合 C 和一个整数 k（k ≥ 1）。要求找到 s 和 t 的最长公共子序列（LCS），但该子序列必须满足以下条件：

1. 对于集合 C 中的每个字符，如果在子序列中出现，则必须连续出现至少 k 次。
2. 子序列中字符的顺序必须与在 s 和 t 中的顺序一致。

例如：

• 输入：s = "aababc", t = "aacabb", C = {'a'}, k = 2
• 输出：4（最长公共子序列为 "aabb"，其中 'a' 连续出现2次）

解题过程

步骤1：问题分析
这是一个带限制条件的LCS问题。普通LCS使用动态规划定义 dp[i][j] 表示 s[0..i-1] 和 t[0..j-1] 的LCS长度。但本题需要额外处理字符连续出现的约束：

• 当我们在子序列中加入字符 ch 时，如果 ch 属于集合 C，则需检查是否满足连续出现 k 次的要求。
• 这要求状态设计能追踪当前已匹配的连续字符及其长度。

步骤2：状态设计
定义 dp[i][j][c][x]：

• i：匹配到 s 的前 i 个字符（0 ≤ i ≤ len(s)）
• j：匹配到 t 的前 j 个字符（0 ≤ j ≤ len(t)）
• c：当前子序列末尾的字符（用整数表示，0 表示无字符，1~26 表示 'a'~'z'）
• x：字符 c 当前已连续出现的次数（1 ≤ x ≤ k，若 x=0 表示未开始连续序列）

状态值表示在满足约束下，当前子序列的最大长度。

步骤3：状态转移

1. 不选当前字符：继承之前状态

   dp[i][j][c][x] = max(dp[i-1][j][c][x], dp[i][j-1][c][x])  
   

2. 当 s[i-1] == t[j-1] 时，考虑将字符 ch = s[i-1] 加入子序列：
   • 若 ch 不属于 C：直接加入，重置连续计数为1（因为非C字符无需连续约束）

     dp[i][j][ch][1] = max(dp[i][j][ch][1], dp[i-1][j-1][任何c][任何x] + 1)  
     

   • 若 ch 属于 C：
     • 如果前一个字符也是 ch 且连续次数 x_prev < k：

       dp[i][j][ch][x_prev+1] = max(..., dp[i-1][j-1][ch][x_prev] + 1)  
       

     • 如果前一个字符不是 ch 或已连续k次：可以开始新序列

       dp[i][j][ch][1] = max(..., dp[i-1][j-1][其他c][其他x] + 1)  
       

     • 特殊：当 x_prev = k-1 时，加入当前字符后连续k次，此时可继续延长或结束序列（因为已满足约束）。

步骤4：初始化和边界

• 初始化 dp[0][0][0][0] = 0，表示空子序列。
• 其他状态初始为负无穷（表示不可达）。

步骤5：结果提取
最终答案是所有 dp[len(s)][len(t)][c][x] 的最大值，其中：

• 若 c 属于 C，则必须 x ≥ k（满足连续k次约束）
• 若 c 不属于 C，则任何 x 均可

步骤6：优化
状态数可能较大（O(n² * 26 * k)），但可通过滚动数组或只记录有效状态来优化空间。

示例验证
以 s = "aababc", t = "aacabb", C = {'a'}, k = 2 为例：

• 有效LCS包括 "aabb"（长度4），其中 'a' 连续2次满足约束。
• 动态规划过程会逐步构建该序列，确保每次添加 'a' 时连续次数达标。

通过以上步骤，我们解决了带字符连续出现约束的LCS问题。