LeetCode 最长重复子串的更换问题
在处理字符串问题时，我们经常会遇到一些具有挑战性的问题，比如今天的这个问题：给定一个字符串 s 和一个整数 k，我们的任务是找到可以通过最多更换 k 个字符来形成的最长重复子串的长度。
我的解决方案可能不是最快速、最有效或最简单的，但我希望通过这个过程深入理解相关的算法。
这个问题要求我们找到可以更换最多 k 个字符来形成重复子串的最长字符串。简单来说，就是允许我们改变字符串中的 k 个字符，使其变成另一个字符，从而创建一个重复的模式。
一种直观的方法是从长度为1的子串开始尝试，并逐步增加子串的长度，直到找到第一个不符合要求的子串。如果子串的长度为 n 且符合要求，那么长度为 n-1 的子串也必然符合要求。但是，这种方法的时间复杂度较高。
有没有更快的方法呢？我们注意到，通过连续检查长度为1、2、3等的子串，我们实际上是在按顺序检查子串的长度。这样的排序顺序让我们有机会使用二分搜索来加快搜索过程。
在这种情况下，我们如何应用二分搜索呢？首先，我们需要确定子串有效性的特征。问题的本质是找到一个子串，其中最常见的字符频率与子串长度之间的差值小于或等于 k。这个差值表示除了最常见字符之外的字符数量。如果这个差值小于或等于 k，我们就可以把这些字符全部更换为最常见的字符，从而形成一个只包含相同字符的子串。
假设子串的长度为 l，最常见的字符频率为 maxFreq。如果长度为 l 的子串有效，那么 l - maxFreq <= k 必然成立。如果长度为 l 的子串有效，那么长度小于 l 的所有子串也都有效。这就意味着，如果找到一个有效的长度 l，所有长度小于 l 的子串也都是有效的。
但是，如果长度为 l 的子串无效，即 l - maxFreq > k，我们能对长度为 l+1 的子串说什么呢？显然，l + 1 - maxFreq > l - maxFreq > k，这意味着如果长度为 l 的子串无效，那么所有长度大于 l 的子串也都无效。
借助这些信息，我们如何应用二分搜索呢？二分搜索通过设置两个边界 lo 和 hi 来定义搜索空间。搜索空间是所有可能的候选解的集合。我们将中间的元素与目标值进行比较，以确定目标值是在搜索空间的前半部分还是后半部分。基于这个比较，我们调整 lo 和 hi 来缩小搜索空间。这个过程一直持续到搜索空间中只剩下一个元素为止，这个元素就是我们要找的答案。
回到我们的问题，我们使用 lo 和 hi 来定义搜索空间的两端：lo 表示到目前为止已知的最长有效子串的长度，hi 表示一个比搜索空间更高的值。我们之所以称这两个事实为不变，是因为我们需要在每一轮搜索后维护它们。
为了缩小搜索空间，我们遵循以下步骤：
- 找到中点。
- 如果我们找到一个长度等于中点值的有效子串，那么所有长度小于中点的子串也都是有效的，但不能是最长的子串。我们知道的最长子串的长度是中点值。为了在保持不变的情况下缩小搜索空间，我们将
lo移动到mid。现在，lo仍然指向到目前为止已知的最长有效子串的长度，而hi保持不变。 - 如果我们找不到长度等于中点值的有效子串，那么所有更长的子串也都无效。因此，最长子串的长度应该小于中点值。我们将搜索空间缩小到从
lo到mid - 1，通过将hi移动到mid。现在hi指针比搜索空间高一个单位，而lo保持不变。 - 我们继续步骤2和3，直到
lo和hi相邻。在这种情况下，lo指向到目前为止已知的最长有效子串的长度，而hi指向一个比搜索空间更高的值。因此，搜索空间中只剩下一个值lo，这可能是最长子串的长度。这就是我们要找的答案。
以下是实现这个算法的JavaScript代码：
function characterReplacement(s: string, k: number): number {
let lo = k, hi = s.length + 1;
while(lo < hi - 1) {
const mid = Math.floor((lo + hi)/2);
if(isValidLength(mid)) {
lo = mid;
}
else {
hi = mid;
}
}
return lo;
function isValidLength(l:number):boolean {
const hashTB:Record<string, number> = {};
let start = 0, maxFreq = 0;
for(let end = 0; end < s.length; end++) {
if(!hashTB[s[end]]) hashTB[s[end]] = 1;
else hashTB[s[end]]++;
if(end - start + 1 > l) {
hashTB[s[start]]--;
start++;
}
if(maxFreq < hashTB[s[end]]) {
maxFreq = hashTB[s[end]];
}
if(l - maxFreq <= k) return true;
}
return false;
}
}
这段代码通过二分搜索和有效性验证函数 isValidLength 来确定最长重复子串的长度。这个过程不仅提高了解决问题的效率，还加深了我们对算法和数据结构的理解。