LeetCode 替换后的最长重复字符题解

LeetCode 替换后的最长重复字符题解题目描述给定一个字符串 s 和一个整数 k最多可以将 k 个字符替换为其他字符返回最长重复字符子串的长度。示例输入s ABAB,k 2输出4解题思路方法字典树 滑动窗口思路使用字典树存储字符出现次数。使用滑动窗口遍历字符串维护窗口内的字符计数。如果窗口内出现次数最多的字符加上 k 小于窗口大小则收缩窗口。复杂度分析时间复杂度O(n)。空间复杂度O(1)。代码实现def character_replacement(s, k): counts {} max_count 0 left 0 result 0 for right in range(len(s)): counts[s[right]] counts.get(s[right], 0) 1 max_count max(max_count, counts[s[right]]) while right - left 1 - max_count k: counts[s[left]] - 1 left 1 result max(result, right - left 1) return result # 测试 def test_character_replacement(): s ABAB k 2 print(character_replacement(s, k)) # 输出4 if __name__ __main__: test_character_replacement()总结替换后的最长重复字符是滑动窗口的典型应用维护窗口内的字符计数找出最长重复字符子串。