Leetcode 424：字符替换最长重复子串代码右指针位置疑问

问题背景 #

在解决Leetcode 424. 替换后的最长重复字符问题时，两段滑动窗口代码仅右指针递增位置不同，但结果差异明显：

• 第一段仅在窗口合法（substr_len - max(char_count.values()) <= k）时移动右指针，测试用例s="AABABBA"、k=1时输出5，不符合预期的4；
• 第二段每次循环先移动右指针再判断窗口合法性，能得到正确结果。
  疑问：为何右指针不能仅在窗口合法时递增，反而必须每次都移动？

第一段代码 #

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l, r = 0, 0
        res = 0
        char_count = {}

        while r < len(s):
            char_count[s[r]] = char_count.get(s[r], 0) + 1
            substr_len = r - l + 1
            
            if substr_len - max(char_count.values()) <= k:
                res = max(res, substr_len)
                r += 1
            else:
                char_count[s[l]] -= 1
                l += 1
            
        return res

测试用例 #

Input
s = "AABABBA"
k = 1

Output: 5
Expected: 4

第二段代码 #

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l, r = 0, 0
        res = 0
        char_count = {}

        while r < len(s):
            char_count[s[r]] = char_count.get(s[r], 0) + 1
            substr_len = r - l + 1
            r += 1
            
            if substr_len - max(char_count.values()) <= k:
                res = max(res, substr_len)
            else:
                char_count[s[l]] -= 1
                l += 1
            
        return res

核心问题分析 #

第一段代码的逻辑漏洞 #

第一段代码的错误在于右指针的移动逻辑违背了滑动窗口的遍历原则：
当窗口不合法时，代码只移动左指针，却始终停留在当前右指针的位置重复处理。这会导致同一个右指针位置的字符被重复计数，进而产生“假合法”的窗口。

拿测试用例举例：当右指针走到索引4（字符'B'）时，窗口为AABAB，此时需要替换2个字符才能全重复，超过k=1，窗口不合法。此时代码会不断移动左指针，但右指针一直停在4的位置，重复累加该位置B的计数。随着左指针右移，窗口长度减小，最终会满足合法条件，但这个窗口是基于重复统计同一个字符得到的错误结果，导致res被错误更新为5。

简单来说，这段代码会让右指针“原地踏步”，重复统计同一字符，从而错误判断窗口合法性。

第二段代码的正确性 #

第二段代码的逻辑是右指针每次循环必移动，保证每个字符只会被处理一次：

1. 先将当前右指针的字符加入计数，计算窗口长度后立刻移动右指针；
2. 如果窗口不合法，就移动左指针缩小窗口，直到窗口重新合法；
3. 窗口合法时更新最大长度。

这种逻辑符合滑动窗口“遍历所有右边界，动态调整左边界”的核心思路：右指针负责遍历整个字符串的每个位置，左指针负责维护当前窗口的合法性，不会出现重复统计同一字符的情况，能正确计算出最长合法窗口长度。

本质区别 #

两段代码的核心差异在于：

• 第一段试图让右指针只停留在合法窗口的位置，导致右指针无法正常遍历所有字符，陷入重复处理同一位置的逻辑漏洞；
• 第二段让右指针遍历所有字符，左指针动态调整窗口，确保每个字符只被处理一次，逻辑完全符合滑动窗口的设计初衷。

内容的提问来源于stack exchange，提问作者user123