What is the main pattern used in Longest Repeating Character Replacement?

The main pattern is a sliding window with running state updates, tracking the most frequent character count and adjusting window size.

Can this problem be solved without a hash table?

While possible with brute-force, a hash table allows tracking character frequencies efficiently, keeping the solution linear in time.

What happens if k is zero?

The problem reduces to finding the longest contiguous substring with identical characters without any replacements.

Is the window always shrunk when replacements exceed k?

Yes, the window is shrunk from the left until the number of required replacements is <= k to maintain a valid substring.

Why track the most frequent character instead of all counts?

Tracking only the maximum frequency avoids recomputing the entire count array for each window adjustment, ensuring O(n) performance.

#424

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。在执行上述操作后，返回包含相同字母的最长子字符串的长度。示例 1：输入： s = "ABAB", k = 2 输出： 4 解释：用两个'A'替换为两个'B',反之…

哈希表字符串滑动窗口

题目描述

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

提示：

1 <= s.length <= 10⁵
s 仅由大写英文字母组成
0 <= k <= s.length

lightbulb

解题思路

方法一：双指针

我们使用一个哈希表 cnt 统计字符串中每个字符出现的次数，使用双指针 l 和 r 维护一个滑动窗口，使得窗口的大小减去出现次数最多的字符的次数，结果不超过 $k$ 。

我们遍历字符串，每次更新窗口的右边界 r，并更新窗口内的字符出现次数，同时更新出现过的字符的最大出现次数 mx。当窗口的大小减去 mx 大于 $k$ 时，我们需要缩小窗口的左边界 l，同时更新窗口内的字符出现次数，直到窗口的大小减去 mx 不大于 $k$ 。

最后，答案为 $n - l$ ，其中 $n$ 为字符串的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        cnt = Counter()
        l = mx = 0
        for r, c in enumerate(s):
            cnt[c] += 1
            mx = max(mx, cnt[c])
            if r - l + 1 - mx > k:
                cnt[s[l]] -= 1
                l += 1
        return len(s) - l

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is processed once when expanding and possibly once when shrinking the window. Space complexity is O(1) since the hash table only tracks counts for uppercase letters, a fixed-size alphabet.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to when to shrink the window; miscalculating replacements can fail the test cases.
question_mark
Tracking the most frequent character is key; using total distinct counts leads to incorrect window evaluation.
question_mark
Optimizing with a hash table prevents repeated scanning of the window, keeping linear performance.

warning

常见陷阱

外企场景

error
Assuming all k replacements are always used; sometimes the optimal window uses fewer than k.
error
Recomputing the most frequent character for every window adjustment, causing O(n^2) complexity.
error
Shrinking the window incorrectly when the required replacements equal k, missing the maximum length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Longest substring with at most k character changes allowing lowercase letters.
arrow_right_alt
Compute longest repeating substring for binary strings with at most k flips.
arrow_right_alt
Determine the minimal k needed to make the entire string a single repeating character.

help

常见问题

外企场景

继续练习

#438 找到字符串中所有字母异位词 #395 至少有 K 个重复字符的最长子串 #567 字符串的排列