最长重复子串（允许最多K个字符不同的最长重复子串） 这道题是“最长重复子串”的一个变种。在标准的最长重复子串问题中，我们通常要求找到两个 完全相同 的子串。而在这个变种中，我们放宽了条件：允许这两个子串在对应位置上最多有 K 个字符不同。换句话说，我们要在给定的单个字符串中，找到两个（可以重叠的）子串，使得这两个子串的“海明距离”（即对应位置不同字符的个数）不超过 K，并且这两个子串的长度相同，我们需要使这个长度尽可能大。 题目描述 输入 ： 一个字符串 s (长度为 n) 一个整数 K (0 ≤ K < n) 输出 ： 一个整数，表示满足条件的 最长重复子串 的长度。这里的“重复子串”定义为：存在两个起始位置不同的子串（长度相同），它们最多有 K 个字符不同。 示例 ： 输入: s = "abcdebb", K = 1 输出: 3 解释: 子串 "bcd" (索引1-3) 和 "bbc" (索引4-6) 长度都为3。它们对应位置比较：b vs b (相同)，c vs b (不同)，d vs c (不同)，共有2个字符不同，大于K=1，不符合。子串 "bc" (索引1-2) 和 "bb" (索引4-5) 长度2，有1个字符不同，符合条件。但更长的“bcd”和“bde”？不存在。更长的“bcd”和“bbc”不符。是否存在长度为3的？我们检查“abc”(0-2)和“bbc”(4-6)，不同字符数为3>1。检查“bcd”(1-3)和“bde”(3-5)，不同字符数为2>1。所以最长长度为2？但实际存在“bcd”(1-3)和“bde”(3-5)比较，长度3，字符：b-b(同), c-d(不同), d-e(不同)，共2个不同，大于K=1。所以不符合。但示例输出是3，让我们重新检查：字符串是"abcdebb"，索引从0开始：a,b,c,d,e,b,b。我们找长度3的子串：(0,1,2) "abc" 和 (4,5,6) "ebb" 比较，不同字符数=3>1。(1,2,3) "bcd" 和 (4,5,6) "ebb" 比较：b-e(不同), c-b(不同), d-b(不同) 共3>1。(2,3,4) "cde" 和 (4,5,6) "ebb" 比较：c-e(不同), d-b(不同), e-b(不同) 3>1。似乎没有长度3且不同数 <=1的。但题目说输出3，可能是另一个例子。我们理解题意即可，下面我会给出一个能输出3的例子。 更清晰的例子： s = "ababc", K = 1 输出: 3 解释: 子串 "aba" (索引0-2) 和 "bab" (索引1-3) 长度3，它们比较：a-b(不同), b-a(不同), a-b(不同) 共3个不同，不符。子串 "ab" (0-1) 和 "ba" (1-2) 不同字符数2>1。实际上，子串 "aba" (0-2) 和 "aba" (2-4)？索引2-4是"abc"，不同。仔细看：长度为3的子串有：0-2 "aba", 1-3 "bab", 2-4 "abc"。比较"aba"和"bab"：不同字符数2>1。比较"aba"和"abc"：不同字符数1（第三个字符a和c不同），满足K=1。所以这两个子串起始位置不同(0和2)，长度3，最多1个字符不同，所以答案是3。 注意 ：这两个子串 可以重叠 ，也可以不重叠。我们的目标是找到最长的长度 L，使得存在两个起始位置 i 和 j (i ≠ j)，子串 s[ i : i+L] 和 s[ j : j+L ] 最多有 K 个字符不同。 解题思路 这个问题可以用多种方法，这里我们讲解一种基于 动态规划 的解法，虽然它不是最高效的（最高效的可以用后缀数组/后缀自动机+二分答案），但动态规划的思路更直观，有助于理解问题本质。 核心难点 直接比较所有可能的子串对 (i, j) 和长度 L 是 O(n³) 的，效率太低。我们需要优化。 动态规划定义 定义 dp[i][j] 表示： 以 s[ i] 结尾的子串和以 s[ j] 结尾的子串，它们从开头到当前位置能够形成的、最多允许 K 个不同字符的公共前缀长度 ？但这不够，因为我们需要记录从某个起点开始，到当前位置的“不同字符数”。 但换个角度，我们实际上是在求：对于固定的长度 L，是否存在两个起始位置 i, j，使得子串 s[ i:i+L] 和 s[ j:j+L ] 的对应位置不同字符数 ≤ K。 我们可以用动态规划来检查 以 i 和 j 开头的两个子串，它们从开头到某个位置，已经有多少个字符不同 。 但更好的方法：用 dp[i][j] 表示： 以 s[ i] 和 s[ j] 结尾的两个子串，在允许最多 K 个不同的前提下，当前匹配的长度 ？不，这样不好处理。 其实我们可以用另一种常见的思路： 二分答案 + 动态规划检查 。 二分答案 ：因为答案（最大长度）具有单调性——如果长度 L 可行，那么更小的长度也一定可行。我们可以二分搜索可能的长度 L。 检查函数 ：对于给定的长度 L，我们需要判断是否存在两个起始位置 i, j (i ≠ j)，使得子串 s[ i:i+L] 和 s[ j:j+L ] 最多有 K 个字符不同。 那么，如何高效实现检查函数呢？ 检查函数的动态规划实现 对于固定的长度 L，我们可以用动态规划来快速计算任意两个起始位置 i 和 j 的子串之间的不同字符数。 定义 diff[i][j] 表示：从位置 i 和 j 开始的、长度为 L 的两个子串，它们之间 不同字符的个数 。但这样定义需要 O(n²) 空间和时间，当 n 很大时不可行。 我们可以优化：我们并不需要所有对的 diff，只需要知道是否存在一对 (i, j) 使得 diff ≤ K。 滑动窗口比较思想 ： 我们可以枚举所有可能的偏移量 d = j - i (d > 0)。对于每个固定的偏移量 d，我们比较所有对应位置：s[ t] 和 s[ t+d ] (t 从 0 到 n-d-1)。这相当于将字符串与自己错位 d 进行比较。 对于固定的 d，我们可以在 O(n) 时间内，通过一个滑动窗口，计算所有长度为 L 的窗口内，s[ t] 和 s[ t+d ] 不同的字符个数。 具体步骤 ： 枚举偏移量 d 从 1 到 n-1。 对于每个 d，我们考虑所有对应的字符对 (s[ i], s[ i+d ])，其中 i 从 0 到 n-d-1。 我们想找到是否存在一个起始位置 p，使得从 p 开始、长度为 L 的窗口中，s[ p ... p+L-1] 和 s[ p+d ... p+d+L-1 ] 这两个子串的不同字符数 ≤ K。 这可以通过维护一个 滑动窗口 内不同字符的计数来实现： 初始化窗口左边界 left = 0，当前不同字符数 cnt = 0。 对于右边界 right 从 0 到 n-d-1，将位置 (right, right+d) 的字符对加入窗口： 如果 s[ right] != s[ right+d ]，则 cnt++。 当 right - left + 1 > L 时，需要将左边界 left 对应的字符对移出窗口： 如果 s[ left] != s[ left+d ]，则 cnt--。 left++。 在窗口长度等于 L 时（即 right - left + 1 == L），检查 cnt ≤ K 是否成立。如果成立，则说明存在一对起始位置 (left, left+d) 满足条件，返回 true。 如果所有 d 都检查完仍未找到，则返回 false。 这个检查函数的时间复杂度是 O(n²)（因为要枚举 d，每个 d 需要 O(n) 时间），在二分答案的外层，总复杂度是 O(n² log n)，对于 n 较小的情况（比如 n ≤ 1000）是可以接受的。 完整算法步骤 二分搜索可能的最大长度 L，范围是 [ 1, n ]。 对于每个猜测的 mid，调用检查函数 check(mid)。 在 check(mid) 中： 枚举偏移量 d 从 1 到 n-1。 对于每个 d，用滑动窗口维护长度为 mid 的窗口内，不同字符的个数 cnt。 当窗口长度等于 mid 时，如果 cnt ≤ K，返回 true。 如果所有 d 和所有窗口都不满足，返回 false。 二分搜索结束后，得到最大长度 L。 举例说明 以 s = "ababc", K = 1 为例。 n = 5。我们二分搜索 L。 猜测 L = 3。 检查 L=3 是否可行。 枚举 d=1: 比较 s[ i] 和 s[ i+1 ]。 滑动窗口维护长度为3的窗口内不同字符数。 窗口 [ 0,2 ]: 比较 (a,b), (b,a), (a,b) → 不同字符数=3（每个位置都不同），cnt=3>K。 窗口 [ 1,3]: 比较 (b,a), (a,b), (b,c) → 不同字符数=3? 我们计算：s[ 1]=b, s[ 2]=a → 不同；s[ 2]=a, s[ 3]=b → 不同；s[ 3]=b, s[ 4]=c → 不同？不对，这里 d=1，所以比较的是 (s[ 1], s[ 2]), (s[ 2], s[ 3]), (s[ 3], s[ 4 ])。即 (b,a) 不同，(a,b) 不同，(b,c) 不同，cnt=3。 没有窗口满足 cnt ≤ 1。 枚举 d=2: 比较 s[ i] 和 s[ i+2 ]。 窗口 [ 0,2]: 比较 (a,c?), 不对，d=2: 比较 s[ 0]&s[ 2]=a,a 相同；s[ 1]&s[ 3]=b,b 相同；s[ 2]&s[ 4 ]=a,c 不同。所以 cnt=1 ≤ K=1，满足！返回 true。 所以 L=3 可行。 二分搜索会继续尝试更大的 L，比如 L=4，检查会发现不可行，所以最终答案是 3。 时间复杂度 二分搜索：O(log n) 检查函数：O(n²) （枚举 d 需 O(n)，每个 d 滑动窗口 O(n)） 总复杂度：O(n² log n) 对于 n 达到 1000 左右是可行的。如果 n 更大，需要更高效的方法（如后缀数组+二分答案+高度数组分组），但这里我们聚焦于动态规划/滑动窗口的思路。 关键点总结 问题转化：允许最多 K 个字符不同的最长重复子串。 二分答案：将求最大长度转化为判定问题。 检查函数：枚举偏移量 d，用滑动窗口快速计算固定长度窗口内的不同字符数。 滑动窗口技巧：维护窗口内不同字符的计数，在 O(n) 时间内完成对一个 d 的检查。 通过这个方法，我们就能在可接受的时间内找到答案。希望这个详细的讲解能帮助你理解这个问题！