LeetCode 424: Longest Repeating Character Replacement — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Sliding Window | Two Pointers | Hash Map | String

The Problem

Find the length of the longest substring containing the same letter that you can get after performing at most k character replacements. You can replace any character in the string with any other uppercase English letter.

Approach

Use a sliding window approach with two pointers to maintain a valid window where the number of characters to replace (window size minus most frequent character count) doesn't exceed k. Expand the window by moving the right pointer and shrink it by moving the left pointer when the replacement count exceeds k.

Time: O(n) · Space: O(1)

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left, right = 0, 0
        max_length = 0
        char_freq = {}
        max_freq = 0

        while right < len(s):
            char_freq[s[right]] = char_freq.get(s[right], 0) + 1
            max_freq = max(max_freq, char_freq[s[right]])

            if (right - left + 1) - max_freq > k:
                char_freq[s[left]] -= 1
                left += 1

            max_length = max(max_length, right - left + 1)
            right += 1

        return max_length