Logo

Kode$word

Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)
Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

Mastering the Sliding Window Pattern with Frequency Optimization

12 views
0
0
Sliding WindowLeetCodeTwo PointersHashMapMedium
Github icon

🔗 Problem Link

LeetCode 424 – Longest Repeating Character Replacement

👉 https://leetcode.com/problems/longest-repeating-character-replacement/

Introduction

When I first looked at this problem, it didn’t immediately feel like a typical sliding window question. It talks about replacing characters, not finding substrings directly.

But the moment you carefully read:

"Return the length of the longest substring containing the same letter after at most k replacements."

That’s when the pattern becomes clear.

This is a variable-size sliding window problem where we try to maintain a valid window under a certain condition.

In this blog, I’ll explain:

  1. The intuition behind the problem
  2. Why sliding window works
  3. The key tricky condition
  4. Step-by-step explanation of the code
  5. Time and space complexity

📌 Problem Understanding

We are allowed to:

  1. Pick any character in the string
  2. Replace it with any uppercase letter
  3. Perform at most k replacements

We need to find the maximum length substring that can become all the same character after at most k changes.

🧠 Key Observation

In any window (substring):

To make all characters the same, we need to:

  1. Keep the most frequent character
  2. Replace all other characters

So the number of replacements required is:

Window Size - Maximum Frequency Character in that Window

If that value is ≤ k, then the window is valid.

This is the most important insight in the entire problem.

🚀 Why Sliding Window?

We are asked for:

  1. Longest substring
  2. Under a constraint
  3. With dynamic window expansion

That is a clear sign of the sliding window pattern.

We use:

  1. i → left pointer
  2. j → right pointer
  3. HashMap → to track character frequencies

💻 Your Code

class Solution {
public int characterReplacement(String s, int k) {
HashMap<Character,Integer> mp = new HashMap<>();
int i= 0;
int j =0;
int co =0;

while(j < s.length()){
mp.put(s.charAt(j),mp.getOrDefault(s.charAt(j),0)+1);
int maxfreq = 0;
for(int a : mp.values()){
maxfreq = Math.max(maxfreq,a);
}
while((j - i +1)-maxfreq > k){ // Tricky part
mp.put(s.charAt(i),mp.get(s.charAt(i))-1);
if(mp.get(s.charAt(i)) == 0){
mp.remove(s.charAt(i));
}
i++;
}
co = Math.max(co,j-i+1);
j++;
}
return co;
}
}

🔍 Step-by-Step Explanation

1️⃣ Expanding the Window

mp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);

We add the current character into the frequency map.

2️⃣ Finding Maximum Frequency

int maxfreq = 0;
for(int a : mp.values()){
maxfreq = Math.max(maxfreq,a);
}

We calculate the highest frequency character inside the window.

Why?

Because that is the character we will keep.

All others will be replaced.

3️⃣ The Most Important Condition (Tricky Part)

while((j - i +1)-maxfreq > k)

Let’s break this:

  1. j - i + 1 → Window size
  2. maxfreq → Count of most frequent character
  3. windowSize - maxfreq → Replacements needed

If replacements needed > k → window is invalid

So we shrink from left.

4️⃣ Shrinking the Window

mp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);
if(mp.get(s.charAt(i)) == 0){
mp.remove(s.charAt(i));
}
i++;

We remove left character and move i forward.

5️⃣ Updating Maximum Length

co = Math.max(co, j - i + 1);

We update our answer whenever the window is valid.

🎯 Why This Works

We always maintain:

(window size - most frequent character count) <= k

That guarantees:

We can convert the entire window into one repeating character using at most k replacements.

⏱ Time and Space Complexity

Time Complexity: O(26 * n) ≈ O(n)

  1. For each character, we scan at most 26 letters.
  2. Since there are only uppercase letters, this is effectively linear.

Space Complexity: O(26)

At most 26 uppercase characters stored.

🔥 Important Optimization Insight

Your solution recalculates maxfreq every time using a loop.

A common optimization is:

  1. Maintain a global maxfreq
  2. Update only when expanding window
  3. Do not recalculate during shrinking

That reduces unnecessary scanning.

But your solution is completely correct and efficient.

🏁 Final Thoughts

This problem teaches:

  1. Sliding Window with condition
  2. Frequency tracking
  3. Window validation logic
  4. Thinking in terms of "how many changes needed"

The key formula to remember:

window size - max frequency <= k

If you truly understand this condition, you unlock many similar problems like:

  1. Longest Substring with K Replacements
  2. Max Consecutive Ones III
  3. Fruit Into Baskets

Related Articles

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

Reversing Letters While Preserving Special Characters in Place

Read Article
Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Using HashMap and Array Optimization to Detect Anagrams Efficiently

Read Article
Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Learn how to find the longest contiguous subarray where each element occurs at most K times using HashMap and sliding window.

Read Article
Longest Substring with K Unique Characters – Efficient Sliding Window Solution

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

Master the sliding window technique using HashMap to find the longest substring with exactly K distinct characters.

Read Article

Ai Assistant Kas