0424.Longest Repeating Character Replacement

• Link: 424. Longest Repeating Character Replacement - Medium
• Track: NeetCode150

Question

• Example 1:
  • Input: s = “ABAB”, k = 2
  • Output: 4
  • Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.

Restate the problem

• Given a string s and an integer k
• Find the longest substring containing the same letter
• Replaced at most k characters
• Return the maximum length

Edge Case

• Single character: len(s) == 1 → return 1

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Sliding window	$O(n)$	$O(1)$
Method 2	Sliding window(use max dic)	$O(n)$	$O(1)$

Method 1 - Sliding window

Even if maxFreq is slightly overestimated, it won’t affect the final answer.”
虚高不会影响最终答案

Approach

• Maintain a sliding window [left, right]
• dic[ch] counts chars in the current window.
• maxfreq = the highest frequency of any single char seen in the window so far (we only increase it).
• Window is valid if:
  window_len - maxfreq <= k
  because that’s how many replacements we need to make all chars the same.
• If invalid, move left to shrink.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Code

from collections import defaultdict
 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        maxfreq = 0
        cnt = defaultdict(int) # {char: freq}
        res = 0
        while right < len(s):
            cnt[s[right]] += 1
            maxfreq = max(maxfreq, cnt[s[right]])
            
            while right - left + 1 - maxfreq > k:
                cnt[s[left]] -= 1
                left += 1
            
            res = max(res, right - left + 1)
            right += 1
        
        return res

Method 2 - Sliding window (use max dic)

Code

from collections import defaultdict
 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        freq = defaultdict(int) # {char:count}
        longest = 0
        res = 0
 
        while right < len(s):
            freq[s[right]] += 1
            longest = max(x for x in freq.values())
 
            while left < right and right - left + 1 - longest > k:
                freq[s[left]] -= 1
                longest = max(x for x in freq.values())
                left += 1
            
            res = max(res, right - left + 1)
            right += 1
        
        return res

---

Common Mistake

• Method 1: Only update maxFreq when expanding right