LeetCode 424 Explained: Longest Repeating Character Replacement Using Sliding Window (Python)

LeetCode 424 – Longest Repeating Character Replacement (Sliding Window)

Today, I solved another LeetCode problem, but this one truly clicked only after watching an intuition-based explanation. I followed this YouTube video to understand the thought process behind the solution:

👉 Watch the intuition video here

Initially, the problem felt tricky because it mixes string manipulation with window resizing logic. But once I understood why sliding window works here, the implementation became much clearer.

---

🧠 Problem Intuition

The goal is to find the longest substring that can be converted into a string of repeating characters by replacing at most k characters.

Instead of checking all substrings (which would be inefficient), we use a sliding window approach. Inside the window:

• We track the frequency of each character.
• We keep note of the most frequent character in the window.
• If the number of characters to replace exceeds k, we shrink the window.

The key insight is this formula:

(window size) - (frequency of most common character) ≤ k

If this condition breaks, the window is no longer valid.

---

⚙️ Code Implementation (Python)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        freq_map = {}
        max_window = 0
        l = 0
        max_freq = 0

        for r in range(len(s)):
            if s[r] not in freq_map:
                freq_map[s[r]] = 1
            else:
                freq_map[s[r]] += 1
            
            max_freq = max(max_freq, freq_map[s[r]])

            if ((r - l) + 1) - max_freq > k:
                freq_map[s[l]] -= 1
                l += 1
            
            max_window = max(max_window, r - l + 1)

        return max_window

---

🔍 Step-by-Step Explanation

• freq_map keeps count of characters inside the current window.
• max_freq stores the count of the most frequent character.
• The window expands using the right pointer.
• If replacements needed exceed k, the left pointer moves forward.
• The maximum valid window size is updated continuously.

Even though max_freq may become outdated when shrinking the window, the logic still works correctly and keeps the algorithm efficient.

---

🚀 Time & Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1) (only uppercase letters)

---

📌 Extra Note

From today onwards, I’ve also started pushing my solutions to GitHub to maintain consistency and visually track my daily activity.

You can find this solution here:

👉 View the solution on GitHub

This problem helped reinforce how powerful the sliding window pattern is when combined with the right intuition.