Why My Sliding Window Solution Was Wrong (And What I Learned)

#algorithms #dsa #coding #leetcode

When I first solved a classic sliding window problem, I was confident my solution was correct.

It passed a few test cases.

But it was fundamentally wrong.

This blog is about:

What mistake I made
Why it failed
And the key insight that fixed everything

The Problem

Given a string s of uppercase letters and an integer k, we can change at most k characters.

👉 Goal:
Find the length of the longest substring that can be converted into all identical characters.

My Initial Thinking

I used a sliding window approach.
window_size - frequency_of_current_character <= k

My logic was:

“If I can convert the current window into the current character within k changes, it should work.”

And honestly—it worked for some test cases like:

"ABBA", k = 2
"AABABBA", k = 1

So I thought I was done.

The Mistake

The mistake was subtle but critical:

👉 I was only considering the frequency of the current (rightmost) character.

But the problem doesn’t ask:

Can I make everything equal to the current character?
It asks:

Can I make everything equal to any character?

Where My Logic Fails

A A A B B
↑ current char = B

Frequency of B = 2
Frequency of A = 3

My logic:
window_size - freq(B) = 5 - 2 = 3

👉 Might reject this window

But correct logic:

window_size - maxFreq = 5 - 3 = 2

👉 This window is actually valid!

🔑 The Key Insight

The correct condition is:

window_size - max_frequency_in_window <= k

👉 Why?

Because:

We keep the most frequent character
Change all others to match it

The Correct Approach

We maintain:

A frequency map
A variable maxFreq (most frequent character in the window)

Correct Code

class Solution {
    longestSubstr(s, k) {
        let left = 0;
        let freq = {};
        let maxFreq = 0;
        let maxLen = 0;

        for (let right = 0; right < s.length; right++) {
            let char = s[right];

            freq[char] = (freq[char] || 0) + 1;

            maxFreq = Math.max(maxFreq, freq[char]);

            let windowSize = right - left + 1;

            if (windowSize - maxFreq > k) {
                freq[s[left]]--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}