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

Source: Dev.to

Problem

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

Approach

Use a sliding‑window (two‑pointer) technique.
Maintain a window [left, right] such that the number of characters that need to be replaced

(window size) – (count of the most frequent character in the window)

does not exceed k.

• Expand the window by moving right and updating the frequency map.
• If the replacement count exceeds k, shrink the window by moving left and adjusting the frequency map.
• Track the maximum window size seen; that is the answer.

Complexity

• Time: O(n) – each character is visited at most twice.
• Space: O(1) – the frequency map holds at most 26 uppercase letters.

Reference Implementation (Python)

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

        while right  k:
                char_freq[s[left]] -= 1
                left += 1

            # update answer
            max_length = max(max_length, right - left + 1)
            right += 1

        return max_length

Visualization

Open interactive visualization – try it yourself with TraceLit and step through every line.