最长公共子序列的变种：带字符限制的最长公共子序列

题目描述：
给定两个字符串s和t，以及一个字符集合C。要求找出s和t的最长公共子序列，且该子序列必须包含集合C中的所有字符（C中每个字符至少出现一次）。集合C中的字符可能重复，但子序列中对应字符的出现次数不能少于C中该字符的出现次数。

解题过程：

1. 问题分析：这是LCS问题的变种，增加了字符限制条件。我们需要在找到的LCS中确保包含特定字符集的所有出现次数要求。

2. 状态定义：
   设dp[i][j][k]表示考虑s的前i个字符、t的前j个字符时，对于字符集C的满足状态k的最长公共子序列长度。

3. 状态压缩：
   由于字符集C可能很大，我们需要用位运算或状态压缩来表示字符包含情况。假设C的大小不超过20，我们可以用位掩码表示。

4. 状态转移：

• 如果s[i-1] == t[j-1]：
  • 该字符在C中：更新包含该字符的状态
  • 该字符不在C中：正常LCS转移
• 如果s[i-1] != t[j-1]：
  • 取不包含s[i-1]或不包含t[j-1]的最大值

5. 具体实现：

• 预处理字符在C中的索引
• 初始化dp数组
• 遍历所有状态，更新最优解
• 最终答案为满足所有字符都包含的状态对应的最大值

6. 优化：

• 使用滚动数组优化空间复杂度
• 预处理字符匹配关系加速计算

这个算法的时间复杂度为O(nm2^|C|)，其中n和m为字符串长度，|C|为限制字符集的大小。