最长公共子序列的变种：带字符出现次数限制的最长公共子序列（进阶版：限制某些字符必须连续出现k次） 题目描述 给定两个字符串s和t，以及一个字符c和一个整数k。要求找出s和t的最长公共子序列（LCS），并且这个公共子序列中，字符c必须连续出现至少k次（即包含一个长度为k的由字符c组成的连续子串）。如果不存在这样的公共子序列，返回0。 例如： s = "abcbcbca", t = "acbcbcaa", c = 'b', k = 3 一个满足条件的LCS是"bcbcbc"（其中包含连续的"bcb"，但'b'不是连续3次） 实际上，满足条件的最长公共子序列是"bcbcb"（长度为5），其中包含连续3个'b'吗？让我们仔细分析。 解题过程 步骤1：理解问题核心 这个问题在标准LCS基础上增加了两个约束： 字符c必须在子序列中出现 字符c必须连续出现至少k次 这意味着我们需要在寻找LCS的过程中，同时跟踪字符c的连续出现情况。 步骤2：状态设计 我们定义dp[ i][ j][ x][ y ]，其中： i: 在s中考虑到第i个字符（1-based indexing） j: 在t中考虑到第j个字符 x: 当前已经连续出现了多少个字符c（0表示当前没有连续出现c） y: 布尔标志，表示是否已经满足了连续k次出现c的条件（0表示未满足，1表示已满足） 步骤3：状态转移方程 情况1：不选择s[ i]和t[ j ]中的任何一个 dp[ i][ j][ x][ y] = max(dp[ i][ j][ x][ y], dp[ i-1][ j-1][ x][ y ]) 情况2：选择s[ i]和t[ j]，且s[ i] == t[ j ] 如果s[ i ] == c： 如果x > 0：说明之前已经在连续出现c 新连续长度 = x + 1 否则：新连续长度 = 1 新y值 = y OR (新连续长度 >= k) dp[ i][ j][ 新连续长度][ 新y值] = max(dp[ i][ j][ 新连续长度][ 新y值 ], dp[ i-1][ j-1][ x][ y ] + 1) 否则（s[ i] != c）： dp[ i][ j][ 0][ y] = max(dp[ i][ j][ 0][ y], dp[ i-1][ j-1][ x][ y ] + 1) 情况3：不选择s[ i ] dp[ i][ j][ x][ y] = max(dp[ i][ j][ x][ y], dp[ i-1][ j][ x][ y ]) 情况4：不选择t[ j ] dp[ i][ j][ x][ y] = max(dp[ i][ j][ x][ y], dp[ i][ j-1][ x][ y ]) 步骤4：初始化 dp[ 0][ 0][ 0][ 0 ] = 0 // 空字符串 其他位置初始化为负无穷（表示不可达） 步骤5：最终答案 答案是所有dp[ n][ m][ x][ 1 ]中的最大值（其中n和m是字符串长度） 如果所有dp[ n][ m][ x][ 1 ]都是负无穷，返回0 步骤6：复杂度分析 时间复杂度：O(n×m×k×2) = O(n×m×k) 空间复杂度：O(n×m×k)（可通过滚动数组优化到O(m×k)） 这个算法通过四维动态规划，在标准LCS的基础上精确跟踪了字符c的连续出现情况，确保找到满足特殊约束的最长公共子序列。