LeetCode 424：最长重复字符替换 — 步骤可视化追踪

Source: Dev.to

问题

在至多进行 k 次字符替换后，找出可以得到的、由相同字母组成的最长子串的长度。你可以将字符串中的任意字符替换为任意其他大写英文字母。

思路

使用滑动窗口（双指针）技术。
维护一个窗口 [left, right]，使得需要替换的字符数量

(窗口大小) – (窗口中出现频率最高的字符的计数)

不超过 k。

• 通过移动 right 并更新频率映射来扩大窗口。
• 如果替换次数超过 k，则通过移动 left 并调整频率映射来收缩窗口。
• 记录出现过的最大窗口大小；这就是答案。

复杂度

• 时间复杂度： O(n) – 每个字符最多被访问两次。
• 空间复杂度： O(1) – 频率映射最多只保存 26 个大写字母。

参考实现（Python）

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left, right = 0, 0
        max_length = 0
        char_freq = {}
        max_freq = 0

        while right  k:
                char_freq[s[left]] -= 1
                left += 1

            # update answer
            max_length = max(max_length, right - left + 1)
            right += 1

        return max_length

可视化

打开交互式可视化 – 亲自使用 TraceLit 进行尝试，并逐行跟踪代码执行过程。