DEV Community

Cover image for The Sliding Window Problem That Taught Me How to Think
Aman Saxena
Aman Saxena

Posted on

The Sliding Window Problem That Taught Me How to Think

#cpp #algorithms #leetcode #programming

It’s been five years since I last touched competitive programming.
Five years since staying up late solving problems just because they were beautiful —
since feeling that unique mix of frustration and excitement only algorithms can give.

Life got busy. Work changed. I moved on.

But recently, I decided to return.
Not as a student grinding contests, but as a developer trying to reconnect with the simple joy of thinking deeply again.

And the very first problem that reminded me why I loved competitive programming was:

Minimum Window Substring

A simple-looking question that gave me more than a challenge— it gave me clarity, humility, and honestly… a spark I had missed.

Returning After Years: The Strange Mix of Rust and Curiosity

Coming back to CP after years felt weird.

My fingers knew how to type fast, but my brain didn’t fire the way it used to.

Problems I would have solved in minutes now took me an hour.

I found myself overthinking simple cases, hesitating with patterns I once memorized.

But in that discomfort, something awakened:

I wasn’t here to be fast anymore.
I was here to enjoy thinking again.

And that mindset made this problem—of all problems—hit differently.

How Minimum Window Substring Helped Me Think Better Again

At first glance, the problem seems mechanical:

“Given strings s and t, find the smallest substring of s containing all chars of t.”

But solving it required something I had lost over the years:

🧠 the ability to break a problem down slowly, clearly, and logically.

I tried brute force.
I tried hashing.
I tried clever tricks that were, honestly, not clever at all.

Nothing worked.

Until one moment, when a simple idea clicked:

This isn’t a substring problem.
It’s a debt repayment problem.

And suddenly the entire algorithm unfolded in front of me.

That feeling—the sudden clarity after hours of confusion— is exactly why returning to CP was worth it.

Understanding the Debt Analogy (The Key Insight)

For t = "ABC" we “owe”:

A:1 B:1 C:1
Enter fullscreen mode Exit fullscreen mode

Now we slide a window across s from left to right.

Every time we encounter a needed character,
we pay off a part of our debt.

When the debt becomes:

A:0 B:0 C:0
Enter fullscreen mode Exit fullscreen mode

We have a valid window.

But valid is not enough—we want the minimum window.
So we try shrinking from the left until the window breaks again.

That balance—expanding greedily, shrinking optimally—
is the core beauty of this problem.

A Simple Diagram That Helped Everything Click

What finally made this problem “click” for me was watching the sliding window evolve across the string — not just a single moment.
The window goes through a complete cycle:

Expand until valid -> Shrink to find local minimum -> Expand again -> Shrink again -> Repeat until the end

Take the smallest valid window ever seen

Here’s the full walkthrough for:

s = A D O B E C O D E B A N C
t = A B C

Step 1:
[A]                   Debt: A0 B1 C1

Step 2:
[A D O B]             Debt: A0 B0 C1

Step 3:
[A D O B E C]         Debt: A0 B0 C0   ✓ First valid window
Enter fullscreen mode Exit fullscreen mode

We finally satisfied all characters in t.
Now time to shrink

Window: [A D O B E C]
         ^
remove A → Debt: A1 B0 C0  → invalid

ADOBEC   (length 6)
Enter fullscreen mode Exit fullscreen mode

Store it and keep moving.

[D O B E C O]
[D O B E C O D]
[D O B E C O D E]
[D O B E C O D E B]

[D O B E C O D E B A]   Debt: A0 B0 C0 → valid again

#shrink
[D O B E C O D E B A]
 ^
remove D → still valid
[O B E C O D E B A]
 ^
remove O → still valid
[B E C O D E B A]
 ^
remove B → Debt: B1 → invalid
BECODEBA  (length 8)

#continue
[E C O D E B A N C]
[B A N C] → valid (Debt satisfied)
[B A N C]
^
remove B → Debt: B1 → invalid
BANC   (length 4)
Enter fullscreen mode Exit fullscreen mode

This is the global minimum across the whole string.

When you watch the window "breathe"—expanding and shrinking—
you start to feel the algorithm working.
And that feeling is something CP had trained me to pay attention to years ago.

C++ Solution (Sliding Window + Frequency Count) 

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.length(), n = t.length();
        if (m < n)
            return "";

        unordered_map<char, int> need;
        for (char c : t)
            need[c]++;
        int required = need.size(); // these are required
        // this to create window
        unordered_map<char, int> window;
        int formed = 0;

        int left = 0, right = 0;
        int minLen = INT_MAX, start = 0;
        while (right < m) {
            char c = s[right];
            window[c]++;

            // check count in need map
            if (need.count(c) && window[c] == need[c]) {
                formed++;
            }
            // once made a window we reduce it
            while (left <= right && formed == required) {
                if ((right - left + 1) < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                char d = s[left];
                window[d]--;
                if (need.count(d) && window[d] < need[d])
                    formed--;

                left++;
            }
            right++;
        }
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)