Space

Open

From Fieldwork

Scales

424. Longest Repeating Character Replacement

leetcodehash-tablesliding-windowmedium

v1

This sliding window solution achieves O(N) time complexity with a subtle optimization: it never actually shrinks the window size; it only shifts it or allows it to grow.

The Key Logic (The "Trick")
You might notice that inside the if block (when the window is invalid), we do not decrement max_freq.

In a standard sliding window, when you remove a character from the left, the "most frequent character" might change, requiring a re-scan of your counts. However, here we are only looking for the longest substring.

If we shrink the window, the window size decreases. We don't care about valid windows smaller than the best one we've already found.
The window only expands (and updates the result) if we find a new max_freq that is higher than before, relative to the window size.
Therefore, max_freq effectively acts as a "historic maximum frequency" for the current window width. We don't need to lower it because the window width will not grow again until we find a frequency that exceeds that historic max.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        max_freq = 0
        left = 0
        
        for right in range(len(s)):
            # Add current character to the count
            char = s[right]
            count[char] = count.get(char, 0) + 1
            
            # Update the count of the most frequent character in the current window
            max_freq = max(max_freq, count[char])
            
            # Validity check:
            # window_length - max_freq = number of replacements needed
            # If replacements needed > k, the window is invalid.
            if (right - left + 1) - max_freq > k:
                # Remove the left character from the map and shift left pointer
                count[s[left]] -= 1
                left += 1
                
        # The window size is (right - left + 1). 
        # Since 'right' ended at len(s) - 1, the max length found is len(s) - left.
        return len(s) - left

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeNov 25, 2025