最长重复字符替换的最长子串（允许最多K次替换）

字数 2542 2025-12-09 06:30:16

最长重复字符替换的最长子串（允许最多K次替换）

题目描述
给定一个字符串 s 和一个整数 k。你可以将字符串中任意位置的字符替换为其他任意字符（每次替换称为一次操作）。你最多可以进行 k 次替换操作。请找出在执行最多 k 次替换操作后，字符串中只包含相同字符的最长子串的长度。

例如：
输入：s = "AABABBA", k = 1
输出：4
解释：将第二个 'A' 替换为 'B'，可以得到 "AAAABBA"，其中最长的只包含相同字符的子串是 "AAAA"，长度为 4。

解题思路

这是一个典型的滑动窗口（双指针）与频率统计结合的线性动态规划（或更准确地说是线性扫描）问题。我们可以在 O(n) 时间内解决。

核心思路是维护一个窗口 [left, right]，并保证窗口内通过替换操作能变成全部相同字符。窗口内出现次数最多的字符是潜在的“目标字符”，我们把窗口内其他字符都替换成它，所需替换次数为：
窗口长度 − 窗口内出现次数最多的字符的出现次数
如果这个替换次数 ≤ k，则窗口合法，可以尝试扩展 right 来扩大窗口；否则，需要收缩 left 来减少窗口长度，直到替换次数 ≤ k。

因为字符集通常只有 26 个大写字母（本题假设大写字母），我们可以用一个长度为 26 的数组来统计窗口内各字符的出现次数，并动态维护当前窗口内出现次数的最大值。

逐步详解

假设字符串 s 长度为 n，字符集大小为 26。

步骤 1：变量定义

用数组 count[26] 记录当前窗口内每个字符的出现次数。
maxCount 记录当前窗口内出现次数最多的字符的出现次数。
left 为窗口左边界（初始 0），right 为窗口右边界（初始 0）。
result 记录最长子串长度（初始 0）。

步骤 2：移动右指针

从 right = 0 到 n-1 遍历字符串。
将 s[right] 加入窗口：count[s[right] − 'A']++。
更新 maxCount = max(maxCount, count[s[right] − 'A'])。

步骤 3：判断窗口合法性
当前窗口长度 = right − left + 1。
如果 窗口长度 − maxCount > k，说明要把窗口内其他字符全部替换成出现最多的字符，需要的操作次数超过了 k，此时窗口不合法，需要收缩左边界：

将 s[left] 从窗口中移除：count[s[left] − 'A']−−。
left++。

注意：收缩左边界后，maxCount 不需要更新，因为：

即使移出窗口的字符恰好是之前出现次数最多的字符，导致 maxCount 可能不再准确，但这不影响判断。因为 maxCount 只会偏大，而我们判断 窗口长度 − maxCount > k 时，maxCount 偏大会让条件更容易不满足（即更容易认为窗口不合法），这只会导致我们可能提前收缩窗口，但最终结果不会错过更优解。这是因为我们只关心最大长度，而 maxCount 偏大时，虽然可能多收缩一点，但下一步 right 右移时会重新调整。

步骤 4：更新结果
每次移动 right 并调整 left 后，窗口都是合法的。此时更新：
result = max(result, right − left + 1)

步骤 5：继续移动 right
重复步骤 2~4，直到 right 遍历完字符串。

实例推演
s = "AABABBA", k = 1

初始化：count[26] 全 0, left=0, right=0, maxCount=0, result=0

right=0, s[0]='A' → count['A']=1, maxCount=1, 窗口长=1, 1−1=0 ≤1 → 合法, result=1
right=1, s[1]='A' → count['A']=2, maxCount=2, 窗口长=2, 2−2=0 ≤1 → 合法, result=2
right=2, s[2]='B' → count['B']=1, maxCount=2, 窗口长=3, 3−2=1 ≤1 → 合法, result=3
right=3, s[3]='A' → count['A']=3, maxCount=3, 窗口长=4, 4−3=1 ≤1 → 合法, result=4
right=4, s[4]='B' → count['B']=2, maxCount=3, 窗口长=5, 5−3=2 >1 → 不合法，移动 left：移出 s[0]='A' → count['A']=2, left=1，窗口长=4, 4−3=1 ≤1 → 合法
right=5, s[5]='B' → count['B']=3, maxCount=3, 窗口长=5, 5−3=2 >1 → 不合法，移出 s[1]='A' → count['A']=1, left=2，窗口长=4, 4−3=1 ≤1 → 合法
right=6, s[6]='A' → count['A']=2, maxCount=3, 窗口长=5, 5−3=2 >1 → 不合法，移出 s[2]='B' → count['B']=2, left=3，窗口长=4, 4−3=1 ≤1 → 合法

结束，result=4。

算法复杂度

时间复杂度：O(n)，每个字符进入窗口一次，离开窗口一次，且统计 maxCount 是 O(1) 的（因为字符集固定）。
空间复杂度：O(1)，因为 count 数组大小固定为 26。

为什么这是线性动态规划？
虽然本题主要用滑动窗口解决，但它也属于线性动态规划的一种变体——我们通过维护窗口状态（字符频次）来动态更新最优解，每次移动右指针相当于状态转移，左指针的移动保证了状态的合法性。这可以看作是一种“双指针动态规划”，是线性动态规划中常见的优化技巧，适用于一维数组上的连续子串/子数组问题。

最长重复字符替换的最长子串（允许最多K次替换）题目描述给定一个字符串 s 和一个整数 k 。你可以将字符串中任意位置的字符替换为其他任意字符（每次替换称为一次操作）。你最多可以进行 k 次替换操作。请找出在执行最多 k 次替换操作后，字符串中只包含相同字符的最长子串的长度。例如：输入：s = "AABABBA", k = 1 输出：4 解释：将第二个 'A' 替换为 'B'，可以得到 "AAAABBA"，其中最长的只包含相同字符的子串是 "AAAA"，长度为 4。解题思路这是一个典型的滑动窗口（双指针）与频率统计结合的线性动态规划（或更准确地说是线性扫描）问题。我们可以在 O(n) 时间内解决。核心思路是维护一个窗口 [ left, right]，并保证窗口内通过替换操作能变成全部相同字符。窗口内出现次数最多的字符是潜在的“目标字符”，我们把窗口内其他字符都替换成它，所需替换次数为：窗口长度 − 窗口内出现次数最多的字符的出现次数如果这个替换次数 ≤ k，则窗口合法，可以尝试扩展 right 来扩大窗口；否则，需要收缩 left 来减少窗口长度，直到替换次数 ≤ k。因为字符集通常只有 26 个大写字母（本题假设大写字母），我们可以用一个长度为 26 的数组来统计窗口内各字符的出现次数，并动态维护当前窗口内出现次数的最大值。逐步详解假设字符串 s 长度为 n，字符集大小为 26。步骤 1：变量定义用数组 count[26] 记录当前窗口内每个字符的出现次数。 maxCount 记录当前窗口内出现次数最多的字符的出现次数。 left 为窗口左边界（初始 0）， right 为窗口右边界（初始 0）。 result 记录最长子串长度（初始 0）。步骤 2：移动右指针从 right = 0 到 n-1 遍历字符串。将 s[right] 加入窗口： count[s[right] − 'A']++ 。更新 maxCount = max(maxCount, count[s[right] − 'A']) 。步骤 3：判断窗口合法性当前窗口长度 = right − left + 1 。如果窗口长度 − maxCount > k ，说明要把窗口内其他字符全部替换成出现最多的字符，需要的操作次数超过了 k，此时窗口不合法，需要收缩左边界：将 s[left] 从窗口中移除： count[s[left] − 'A']−− 。 left++ 。注意：收缩左边界后， maxCount 不需要更新，因为：即使移出窗口的字符恰好是之前出现次数最多的字符，导致 maxCount 可能不再准确，但这不影响判断。因为 maxCount 只会偏大，而我们判断窗口长度 − maxCount > k 时， maxCount 偏大会让条件更容易不满足（即更容易认为窗口不合法），这只会导致我们可能提前收缩窗口，但最终结果不会错过更优解。这是因为我们只关心最大长度，而 maxCount 偏大时，虽然可能多收缩一点，但下一步 right 右移时会重新调整。步骤 4：更新结果每次移动 right 并调整 left 后，窗口都是合法的。此时更新： result = max(result, right − left + 1) 步骤 5：继续移动 right 重复步骤 2~4，直到 right 遍历完字符串。实例推演 s = "AABABBA", k = 1 初始化：count[ 26 ] 全 0, left=0, right=0, maxCount=0, result=0 right=0, s[ 0]='A' → count[ 'A' ]=1, maxCount=1, 窗口长=1, 1−1=0 ≤1 → 合法, result=1 right=1, s[ 1]='A' → count[ 'A' ]=2, maxCount=2, 窗口长=2, 2−2=0 ≤1 → 合法, result=2 right=2, s[ 2]='B' → count[ 'B' ]=1, maxCount=2, 窗口长=3, 3−2=1 ≤1 → 合法, result=3 right=3, s[ 3]='A' → count[ 'A' ]=3, maxCount=3, 窗口长=4, 4−3=1 ≤1 → 合法, result=4 right=4, s[ 4]='B' → count[ 'B']=2, maxCount=3, 窗口长=5, 5−3=2 >1 → 不合法，移动 left：移出 s[ 0]='A' → count[ 'A' ]=2, left=1，窗口长=4, 4−3=1 ≤1 → 合法 right=5, s[ 5]='B' → count[ 'B']=3, maxCount=3, 窗口长=5, 5−3=2 >1 → 不合法，移出 s[ 1]='A' → count[ 'A' ]=1, left=2，窗口长=4, 4−3=1 ≤1 → 合法 right=6, s[ 6]='A' → count[ 'A']=2, maxCount=3, 窗口长=5, 5−3=2 >1 → 不合法，移出 s[ 2]='B' → count[ 'B' ]=2, left=3，窗口长=4, 4−3=1 ≤1 → 合法结束，result=4。算法复杂度时间复杂度：O(n)，每个字符进入窗口一次，离开窗口一次，且统计 maxCount 是 O(1) 的（因为字符集固定）。空间复杂度：O(1)，因为 count 数组大小固定为 26。为什么这是线性动态规划？虽然本题主要用滑动窗口解决，但它也属于线性动态规划的一种变体——我们通过维护窗口状态（字符频次）来动态更新最优解，每次移动右指针相当于状态转移，左指针的移动保证了状态的合法性。这可以看作是一种“双指针动态规划”，是线性动态规划中常见的优化技巧，适用于一维数组上的连续子串/子数组问题。