💬 Discord
Sign In
NeetCode #231LC-424MediumSliding WindowBlind 75NC 150NC 250
← Back to All Problems

#231 · #424 · Longest Repeating Character Replacement(替换后的最长重复字符)

📌 Problem Statement & Constraints

You are given a string s and an integer k. You may replace at most k characters with any uppercase letter. Return the length of the longest substring containing the same letter after at most k replacements. Constraints: 1 <= s.length <= 10^5, 0 <= k <= s.length; s consists of uppercase letters.

💡 Core Algorithmic Approaches

  1. For a window, the number of replacements needed is window_length - max_frequency_in_window.
  2. Expand the window to the right, tracking the maximum character frequency inside it.
  3. When the required replacements exceed k, shrink from the left by one.
  4. Key trick: never decrease maxf. It only needs to be an upper bound, because the window size never needs to shrink below the best answer already found -- this keeps the algorithm a true single pass.

💻 Benchmark Python3 Implementation

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        from collections import Counter
        cnt = Counter()
        l = 0
        maxf = 0                       # max frequency seen in any window so far
        best = 0
        for r, ch in enumerate(s):
            cnt[ch] += 1
            maxf = max(maxf, cnt[ch])
            # window is valid when (length - maxf) <= k
            if (r - l + 1) - maxf > k:
                cnt[s[l]] -= 1
                l += 1
            best = max(best, r - l + 1)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) counter operations.
💾 Space Complexity
O(1): the counter holds at most 26 entries.

⚠️ Interview Pitfalls & Follow-ups

  • Decrementing maxf when shrinking: not only unnecessary but wrong for the standard formulation -- maxf is used as a monotone upper bound, and recomputing it exactly would cost O(26) per step and break the amortised argument.
  • Using a while loop to shrink until valid: it still works but is O(n) per step in the worst case if maxf is recomputed; with the monotone bound a single if suffices.
  • Forgetting that the answer is the window length, not the count of replacements: the window may not be fully uniform, but its length is what matters.
  • Assuming the replaced characters must all become the same letter: they do -- the target letter is the window's most frequent one.