线性动态规划：统计只含单一字符的最长子串的变种——最多允许替换k次字符的最长子串
字数 2273 2025-12-13 02:36:05

线性动态规划：统计只含单一字符的最长子串的变种——最多允许替换k次字符的最长子串

题目描述

给定一个字符串 s（仅由小写英文字母组成）和一个整数 k。你可以在字符串中选择一个子串，并执行最多 k 次字符替换操作（将子串中的任意字符替换为另一个任意字符），目标是使得替换后的子串中的所有字符都相同。请问在最多允许 k 次替换的条件下，能够获得的最长全相同字符子串的长度是多少？

例如：

  • 输入：s = "AABABBA", k = 1
  • 输出：4
  • 解释：可以将中间的 'A' 替换为 'B'，得到 "AABBBBA"，子串 "ABBB"（替换一次后变成 "BBBB"）长度为 4。

解题思路

这是一个典型的“滑动窗口”配合动态规划思想的题目，我们可以利用双指针（左指针 L 和右指针 R）维护一个窗口，并动态统计窗口中某个字符出现的最大频次，通过替换其他字符来使窗口内所有字符相同，并检查替换次数是否超过 k。

核心思路：

  1. 维护窗口 [L, R]，并统计窗口内每个字符出现的次数。
  2. 在窗口内找到出现次数最多的字符（记其出现次数为 maxFreq），那么将窗口内其他字符都替换为该字符所需的替换次数为 (窗口长度 - maxFreq)。
  3. 如果 (窗口长度 - maxFreq) > k，说明替换次数超过了允许值，此时需要缩小窗口（移动左指针 L），直到替换次数 ≤ k。
  4. 每次扩大右指针 R 时，更新最大长度结果。

具体步骤与详解

步骤 1：初始化变量

  • 使用一个长度为 26 的数组 count（因为只有大写字母，但在实际代码中可根据字符集调整）来统计窗口内每个字符的出现次数。
  • 初始化左指针 L = 0，当前窗口内出现最多的字符频次 maxFreq = 0，以及最终答案 ans = 0。

步骤 2：遍历字符串（移动右指针）

用右指针 R 从 0 到 n-1 遍历字符串：

  • 将字符 s[R] 加入窗口，即 count[s[R]-'A']++。
  • 更新 maxFreq = max(maxFreq, count[s[R]-'A'])。注意：maxFreq 是当前窗口内所有字符中出现最多的次数。

步骤 3：检查窗口合法性

计算当前窗口长度 winLen = R - L + 1。

  • 如果 winLen - maxFreq > k，说明当前窗口内替换成相同字符所需的最小替换次数超过了 k，需要缩小窗口。
  • 缩小窗口：将左指针字符移出窗口（count[s[L]-'A']--），并右移左指针 L++。
  • 注意：缩小窗口后，maxFreq 可能不再准确，但它仍然表示窗口内某个字符的最大频次。即使它不是当前窗口的真正最大频次，我们也不更新它，因为：
    • 我们只关心窗口长度能否更大，而 maxFreq 偏大只会使窗口更可能满足条件，所以不影响正确性。
    • 如果 maxFreq 因左移而减小，则窗口长度也会相应减小，不会导致最终答案偏大。

步骤 4：更新答案

在每次移动右指针并调整窗口后，当前窗口长度 winLen 满足替换次数 ≤ k。更新 ans = max(ans, winLen)。

步骤 5：返回结果

遍历结束后，ans 即为所求的最长子串长度。

举例说明

以 s = "AABABBA", k = 1 为例：

  • 初始化 L = 0, maxFreq = 0, ans = 0。
  • R = 0: 字符 'A'，count['A']=1, maxFreq=1, winLen=1, 替换次数 1-1=0 ≤1，ans=1。
  • R = 1: 字符 'A'，count['A']=2, maxFreq=2, winLen=2, 替换次数 2-2=0 ≤1，ans=2。
  • R = 2: 字符 'B'，count['B']=1, maxFreq=2, winLen=3, 替换次数 3-2=1 ≤1，ans=3。
  • R = 3: 字符 'A'，count['A']=3, maxFreq=3, winLen=4, 替换次数 4-3=1 ≤1，ans=4。
  • R = 4: 字符 'B'，count['B']=2, maxFreq=3, winLen=5, 替换次数 5-3=2 >1，不满足，左移 L：
    • 移出 s[0]='A', count['A']=2, L=1, winLen=4, 替换次数 4-3=1 ≤1，满足。
  • 继续移动 R 到结束，窗口长度不再超过 4，最终 ans=4。

算法复杂度

  • 时间复杂度：O(n)，其中 n 是字符串长度。左右指针各遍历一次字符串。
  • 空间复杂度：O(1) 或 O(字符集大小)，这里字符集大小为 26。

关键点

  • 不直接枚举替换哪个字符，而是通过维护窗口内最大频次字符，间接得到最小替换次数。
  • maxFreq 不随左指针移动而立即更新，这是为了简化计算，同时不影响正确性，因为 maxFreq 可能变小，但窗口长度也会变小，不会使答案变大。

总结

通过滑动窗口和频次统计，我们巧妙地避免了枚举替换字符的种类，将问题转化为维护一个满足替换次数限制的最大窗口，从而在线性时间内解决了问题。

线性动态规划：统计只含单一字符的最长子串的变种——最多允许替换k次字符的最长子串 题目描述 给定一个字符串 s （仅由小写英文字母组成）和一个整数 k 。你可以在字符串中选择一个子串，并执行最多 k 次字符替换操作（将子串中的任意字符替换为另一个任意字符），目标是使得替换后的子串中的所有字符都相同。请问在最多允许 k 次替换的条件下，能够获得的最长全相同字符子串的长度是多少？ 例如： 输入： s = "AABABBA" , k = 1 输出： 4 解释：可以将中间的 'A' 替换为 'B' ，得到 "AABBBBA" ，子串 "ABBB" （替换一次后变成 "BBBB" ）长度为 4。 解题思路 这是一个典型的“滑动窗口”配合动态规划思想的题目，我们可以利用双指针（左指针 L 和右指针 R ）维护一个窗口，并动态统计窗口中某个字符出现的最大频次，通过替换其他字符来使窗口内所有字符相同，并检查替换次数是否超过 k 。 核心思路 ： 维护窗口 [L, R] ，并统计窗口内每个字符出现的次数。 在窗口内找到出现次数最多的字符（记其出现次数为 maxFreq ），那么将窗口内其他字符都替换为该字符所需的替换次数为 (窗口长度 - maxFreq) 。 如果 (窗口长度 - maxFreq) > k ，说明替换次数超过了允许值，此时需要缩小窗口（移动左指针 L ），直到替换次数 ≤ k 。 每次扩大右指针 R 时，更新最大长度结果。 具体步骤与详解 步骤 1：初始化变量 使用一个长度为 26 的数组 count （因为只有大写字母，但在实际代码中可根据字符集调整）来统计窗口内每个字符的出现次数。 初始化左指针 L = 0 ，当前窗口内出现最多的字符频次 maxFreq = 0 ，以及最终答案 ans = 0 。 步骤 2：遍历字符串（移动右指针） 用右指针 R 从 0 到 n-1 遍历字符串： 将字符 s[R] 加入窗口，即 count[s[R]-'A']++ 。 更新 maxFreq = max(maxFreq, count[s[R]-'A']) 。注意： maxFreq 是当前窗口内所有字符中出现最多的次数。 步骤 3：检查窗口合法性 计算当前窗口长度 winLen = R - L + 1 。 如果 winLen - maxFreq > k ，说明当前窗口内替换成相同字符所需的最小替换次数超过了 k ，需要缩小窗口。 缩小窗口：将左指针字符移出窗口（ count[s[L]-'A']-- ），并右移左指针 L++ 。 注意：缩小窗口后， maxFreq 可能不再准确，但它仍然表示窗口内某个字符的最大频次。即使它不是当前窗口的真正最大频次，我们也不更新它，因为： 我们只关心窗口长度能否更大，而 maxFreq 偏大只会使窗口更可能满足条件，所以不影响正确性。 如果 maxFreq 因左移而减小，则窗口长度也会相应减小，不会导致最终答案偏大。 步骤 4：更新答案 在每次移动右指针并调整窗口后，当前窗口长度 winLen 满足替换次数 ≤ k 。更新 ans = max(ans, winLen) 。 步骤 5：返回结果 遍历结束后， ans 即为所求的最长子串长度。 举例说明 以 s = "AABABBA" , k = 1 为例： 初始化 L = 0 , maxFreq = 0 , ans = 0 。 R = 0 : 字符 'A' ， count['A']=1 , maxFreq=1 , winLen=1 , 替换次数 1-1=0 ≤1 ， ans=1 。 R = 1 : 字符 'A' ， count['A']=2 , maxFreq=2 , winLen=2 , 替换次数 2-2=0 ≤1 ， ans=2 。 R = 2 : 字符 'B' ， count['B']=1 , maxFreq=2 , winLen=3 , 替换次数 3-2=1 ≤1 ， ans=3 。 R = 3 : 字符 'A' ， count['A']=3 , maxFreq=3 , winLen=4 , 替换次数 4-3=1 ≤1 ， ans=4 。 R = 4 : 字符 'B' ， count['B']=2 , maxFreq=3 , winLen=5 , 替换次数 5-3=2 >1 ，不满足，左移 L ： 移出 s[0]='A' , count['A']=2 , L=1 , winLen=4 , 替换次数 4-3=1 ≤1 ，满足。 继续移动 R 到结束，窗口长度不再超过 4，最终 ans=4 。 算法复杂度 时间复杂度：O(n)，其中 n 是字符串长度。左右指针各遍历一次字符串。 空间复杂度：O(1) 或 O(字符集大小)，这里字符集大小为 26。 关键点 不直接枚举替换哪个字符，而是通过维护窗口内最大频次字符，间接得到最小替换次数。 maxFreq 不随左指针移动而立即更新，这是为了简化计算，同时不影响正确性，因为 maxFreq 可能变小，但窗口长度也会变小，不会使答案变大。 总结 通过滑动窗口和频次统计，我们巧妙地避免了枚举替换字符的种类，将问题转化为维护一个满足替换次数限制的最大窗口，从而在线性时间内解决了问题。