最长重复子串的变种：允许最多k次字符替换的最长重复子串（进阶版：替换操作有不同代价，且替换后字符必须与原始字符不同）

题目描述

给定一个字符串 s，以及一个整数 k。你可以在字符串中选择一个子串，并对该子串中的字符进行最多 k 次替换操作。每次替换操作可以将一个字符替换为另一个字符（替换后的字符必须与原字符不同，且替换操作有不同的代价，代价由给定的代价矩阵决定）。目标是找到一个最长的子串，使得在进行最多 k 次替换操作后，该子串中的所有字符都相同。求这个最长子串的长度。

注意：

1. 替换操作只针对选定的子串内的字符进行。
2. 每次替换的代价可能不同（例如，将字符 'a' 替换为 'b' 的代价可能不同于将 'a' 替换为 'c' 的代价）。
3. 替换后的字符必须与原字符不同（即不允许替换为相同字符）。
4. 你只能进行最多 k 次替换操作，而不是总代价不超过某个值。这里的 k 是操作次数限制。

解题思路

这是一个典型的“滑动窗口”与“动态规划”结合的问题，但更侧重于滑动窗口（双指针）策略。核心思想是：对于每个可能的字符作为目标字符（即希望子串最终全部变成的字符），使用滑动窗口来找到在最多 k 次替换下能构成的最长子串。

步骤1：问题转化

我们最终的子串将全部由某个字符 target 组成。对于窗口内的子串，我们需要将其中所有不是 target 的字符替换为 target。但是，由于替换操作有不同代价，且替换后必须不同，我们实际上在选择 target 时，需要考虑窗口内非 target 字符的替换代价。然而，题目限制的是替换操作次数 k，而不是总代价。因此，对于每个非 target 字符，无论其替换代价是多少，都只计数为一次操作。

这样一来，问题简化为：对于每个字符 c（从 'a' 到 'z'，假设字符串只包含小写字母），找到最长的子串，使得该子串中非 c 的字符数量不超过 k。

步骤2：滑动窗口算法（对于固定的目标字符 target）

1. 使用两个指针 left 和 right 表示窗口的左右边界。
2. 初始化 left = 0，count_non_target = 0（记录窗口中非 target 字符的数量）。
3. 遍历 right 从 0 到 n-1：
   • 如果 s[right] != target，则 count_non_target++。
   • 当 count_non_target > k 时，说明当前窗口内需要替换的字符数超过了 k，需要收缩左边界：
     • 如果 s[left] != target，则 count_non_target--（因为移出了一个非 target 字符）。
     • left++。
   • 此时窗口 [left, right] 是有效的（替换次数 ≤ k）。更新最大长度：max_len = max(max_len, right - left + 1)。

对每个可能的 target（'a' 到 'z'）都执行上述过程，取所有结果中的最大值。

步骤3：处理替换代价的限制（进阶部分）

题目中提到了“替换操作有不同的代价”，但限制的是操作次数 k，而不是总代价。因此，替换代价实际上不影响最长子串的计算——我们只需要关心需要替换的字符数量，而不必关心具体代价。
注意：如果替换代价会影响（例如，总代价不能超过某个值），那么问题将变得更加复杂，需要结合动态规划或背包思想。但根据题目描述，这里只限制操作次数，所以忽略代价。

步骤4：考虑“替换后字符必须与原字符不同”

这个条件实际上隐含在操作中：当我们把一个字符替换为 target 时，如果该字符本来就是 target，则不需要替换。因此，在计数时，我们只对非 target 字符计数，这自然满足了“替换后字符不同”的条件（因为 target 字符不变，非 target 字符变为 target，肯定不同）。

算法实现（伪代码）

函数 longest_repeating_substring(s, k):
    n = s的长度
    max_len = 0
    对于 每个字符 target 在 ['a'..'z']:
        left = 0
        count_non_target = 0
        对于 right 从 0 到 n-1:
            如果 s[right] != target:
                count_non_target += 1
            当 count_non_target > k:
                如果 s[left] != target:
                    count_non_target -= 1
                left += 1
            max_len = max(max_len, right - left + 1)
    返回 max_len

复杂度分析

• 外层循环遍历26种字符。
• 内层滑动窗口遍历字符串一次，每次操作是 O(1)。
• 总时间复杂度：O(26 * n) = O(n)，其中 n 是字符串长度。
• 空间复杂度：O(1)，只使用了常数个变量。

例子演示

假设 s = "AABABBA", k = 1。
我们以 target = 'A' 为例：

• right=0, s[0]='A'，count=0，窗口 [0,0]，长度=1。
• right=1, s[1]='A'，count=0，窗口 [0,1]，长度=2。
• right=2, s[2]='B'，count=1，窗口 [0,2]，长度=3。
• right=3, s[3]='A'，count=1，窗口 [0,3]，长度=4。
• right=4, s[4]='B'，count=2 > k=1，收缩 left：s[left]='A'，left=1，count 仍为2；继续收缩：s[left]='A'，left=2，count=1，窗口 [2,4]，长度=3。
• right=5, s[5]='B'，count=2 > k，收缩：s[left]='B'，left=3，count=1，窗口 [3,5]，长度=3。
• right=6, s[6]='A'，count=1，窗口 [3,6]，长度=4。

最大长度是4（如窗口 "ABAB" 替换第二个 'B' 为 'A' 得到 "AAAA"）。
再尝试 target = 'B' 等，最终得到全局最大值是4。

总结

这个问题的核心是将“最多k次替换”转化为“窗口中非目标字符的数量不超过k”，从而可以使用滑动窗口高效求解。虽然题目提到了“替换代价不同”，但由于限制的是操作次数而非总代价，因此代价不影响最终结果。如果题目改为“总代价不超过C”，则需要维护窗口内所有非目标字符的替换代价之和，并利用有序数据结构（如优先队列）来动态维护，复杂度会升高到 O(n log n)。