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

题目描述
给定两个字符串 s 和 t，以及一个整数 k。要求找到 s 和 t 的最长公共子序列（LCS），但附加条件：在公共子序列中，如果某个字符连续出现，则必须至少连续出现 k 次（即不允许出现连续次数少于 k 的相同字符段）。例如，若 k=3，则子序列中 "aa" 是无效的（因为连续出现2次 < 3），但 "aaa" 或 "aaaa" 是有效的。

解题过程

1. 问题分析
   传统 LCS 使用动态规划定义 dp[i][j] 表示 s[0..i-1] 和 t[0..j-1] 的 LCS 长度。本题需额外记录连续字符的出现次数，并确保连续段长度 ≥ k。

2. 状态设计
   定义 dp[i][j][c][cnt]：

   • 考虑 s 的前 i 个字符和 t 的前 j 个字符。
   • c 表示当前公共子序列的最后一个字符（用整数表示，如 'a'=0, 'b'=1...），若暂无字符则设为特殊值（如 -1）。
   • cnt 表示字符 c 在当前公共子序列末尾的连续出现次数。
     状态值表示满足条件的最长子序列长度。

3. 状态转移

   • 情况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（新字符段）：需检查旧段是否有效（若 c != -1 且 cnt < k，则旧段无效，不能转移）；有效时新段长度=1。
     • 若 ch == c（延续旧段）：新连续次数 new_cnt = cnt + 1。
       转移方程：

     if ch == c:
         dp[i][j][c][new_cnt] = max(dp[i][j][c][new_cnt], dp[i-1][j-1][c][cnt] + 1)
     else:
         if c == -1 or cnt >= k:  # 旧段有效或无旧段
             dp[i][j][ch][1] = max(dp[i][j][ch][1], dp[i-1][j-1][c][cnt] + 1)
     

4. 初始化和答案提取

   • 初始化：dp[0][0][-1][0] = 0 表示空子序列。
   • 答案：所有 dp[len(s)][len(t)][c][cnt] 的最大值，且需满足 cnt >= k 或 c == -1（空序列）。

5. 优化
   状态数可能较大，可滚动数组优化空间。实际实现时需注意无效状态的剪枝（如 cnt > k 时只需保留 cnt = k，因为更长连续段不影响后续转移）。

示例
设 s = "aabba", t = "aacaa", k=2。
有效 LCS 示例："aaa"（连续3次 ≥2），无效示例："aa"（虽连续但次数=2? 注意：2≥2 有效，但若取 "aa" 则长度短于 "aaa"）。
通过 DP 计算可得最长有效子序列为 "aaa" 或 "aa"（但 "aa" 长度较短），最终答案为 3。

总结
本题通过扩展 LCS 状态，加入末尾字符及其连续次数，确保了连续段长度的限制。关键点在于正确处理字符段切换时的有效性检查。