python - Leetcode 424.最长重复字符替换: Right Pointer Incrementation

Question

我正在尝试解决Leetcode 424. Longest Repeating Character Replacement 。 为什么这段代码不起作用，我无法理解它。

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

两个代码之间的区别在于右指针递增的位置。如果substr_len - max(char_count.values()) <= k，右指针不应该只增加吗？ ？这不是第一个代码正在做的事情吗？而第二个代码总是递增右指针，即使 substr_len > k ？

Answer 1

问题是万一substr_len - max(char_count.values()) <= k为 false，您只是减少左边界字符数，同时保持相同的右边界位置。因此，在下一次迭代中，您将再次计算正确的边界字符。您需要减少 char_count[s[r]] -= 1以及 else block 中。

您的第二个代码之所以有效，是因为您正在搜索最大可能的子字符串长度。在第一次进入 else block 之前，第一个和第二个代码的行为相同。当您输入 else block 时，您将移动左边框和右边框(而不是仅移动左边框)。但这不是问题，因为您对长度较短的子字符串不感兴趣。您永远不必减少算法中的间隔长度。

我希望这是可以理解的。如果您需要更多解释，请评论:)