统计同构子字符串的数目问题（字符替换成本版本） 题目描述： 给定一个字符串s和一个整数k，你可以执行任意次操作，每次操作可以将字符串中的一个字符替换为另一个字符，每次替换的成本为1。请计算在总成本不超过k的情况下，该字符串中同构子字符串的最大可能数量。 同构子字符串定义为所有字符都相同的连续子串。例如，"aaa"、"bb"、"c"都是同构子字符串。 解题过程： 问题分析： 我们需要找到在最多k次替换后，字符串中能够得到的最大同构子字符串数量 同构子字符串是连续的相同字符组成的子串 每个替换操作成本为1，总成本不能超过k 动态规划状态定义： 定义dp[ i][ j][ c ]表示考虑前i个字符，使用了j次替换，且第i个字符被替换为字符c（c是字符集中的一个字符）时，能够得到的最大同构子字符串数量。 状态转移方程： 对于每个位置i，我们考虑两种情况： 情况1：当前字符与上一个字符相同 如果s[ i ] == c（即当前字符就是目标字符c，不需要替换）： dp[ i][ j][ c] = dp[ i-1][ j][ c ] + 0 // 不增加新的同构子串 如果s[ i] != c（需要替换）： dp[ i][ j][ c] = dp[ i-1][ j-1][ c ] + 0 // 需要消耗1次替换 情况2：当前字符与上一个字符不同 如果s[ i ] == c（不需要替换）： dp[ i][ j][ c] = max(dp[ i-1][ j][ prev_ c ]) + 1 // 增加新的同构子串 如果s[ i] != c（需要替换）： dp[ i][ j][ c] = max(dp[ i-1][ j-1][ prev_ c ]) + 1 // 需要消耗1次替换 其中prev_ c表示前一个位置可能的字符。 初始化： dp[ 0][ 0][ s[ 0] ] = 1 // 第一个字符不替换 dp[ 0][ 1][ c] = 1 // 第一个字符替换为任意字符c ≠ s[ 0 ] 其他情况初始化为负无穷 算法步骤： 步骤1：初始化dp数组 步骤2：遍历每个位置i从1到n-1 步骤3：遍历替换次数j从0到k 步骤4：遍历当前字符c（所有可能的字符） 步骤5：遍历前一个字符prev_ c（所有可能的字符） 步骤6：根据状态转移方程更新dp值 步骤7：最终答案为max(dp[ n-1][ j][ c ])，其中0≤j≤k，c为任意字符 优化： 我们可以将字符集限制为实际出现在字符串中的字符加上可能替换的字符 使用滚动数组优化空间复杂度 时间复杂度：O(n×k×m²)，其中n为字符串长度，k为最大替换次数，m为字符集大小 这个问题的关键在于理解：当字符发生变化时，同构子字符串数量会增加1，而保持字符相同时不会增加新的同构子字符串。通过动态规划，我们可以找到在有限替换次数下最大化同构子字符串数量的最优策略。