Minimum Window Substring

Table of Contents +

This one is the hard sibling of the sliding window family. People freeze when they see it. The interviewer wants to see if you can grow a window until it has everything you need. Then shrink it to make it as small as possible. That grow-then-shrink dance is the whole trick. Once you feel it, this problem stops being scary.

🎯 The Problem

You get two strings, s and t. You have to find the smallest part of s that holds every letter of t.

A substring is a run of characters with nothing skipped.
The window must hold every letter of t.
Counts matter. If t has two o letters, the window needs two o letters.
You want the shortest such window.
If no window works, return an empty string.

Let us say s is "ADOBECODEBANC" and t is "ABC". The smallest part of s that holds an A, a B, and a C is "BANC". So the answer is "BANC".

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Explanation: "BANC" is the shortest substring of s that contains A, B, and C.

Here is what we are hunting for. The window must cover every needed letter, and we want it as short as possible.

🐢 Approach 1: Check Every Substring (Brute Force)

Try every possible substring of s and keep the shortest valid one.

The idea:

Pick every start index and every end index.
That gives every substring of s.

How it works:

For each substring, count its letters.
Check if it holds every letter of t with the right counts.
Keep the shortest substring that passes.

Why it is weak:

There are about n² substrings.
Each check scans the letters again.
Time drifts to O(n³) or O(n²·k). Far too slow on long strings.

Here is the brute-force code for that idea:

from collections import Counter


def min_window(s, t):
    need = Counter(t)
    best = ""
    for left in range(len(s)):
        have = Counter()
        for right in range(left, len(s)):
            have[s[right]] += 1
            if all(have[ch] >= need[ch] for ch in need):
                candidate = s[left:right + 1]
                if best == "" or len(candidate) < len(best):
                    best = candidate
                break
    return best

🐌 Approach 2: Expand From Each Start (Better)

The idea in one line: fix the left edge, then grow the right edge only until the window first becomes valid.

The idea:

For each left index, push the right edge forward.
Stop the moment the window holds every letter of t.

How it works:

Keep a running count of letters in the current window.
Once valid, record the length and move the left edge forward.
No need to rescan the whole substring each time.

Why it is better:

It stops early instead of building every full substring.
It avoids the innermost rescan of brute force.

Why it is still weak:

The left edge restarts the right scan each time.
That is still about O(n²) in the worst case.

Here is the expand-from-each-start code:

from collections import Counter


def min_window(s, t):
    need = Counter(t)
    best = ""

    for left in range(len(s)):
        missing = len(t)
        have = Counter()
        for right in range(left, len(s)):
            ch = s[right]
            have[ch] += 1
            if have[ch] <= need[ch]:
                missing -= 1
            if missing == 0:
                candidate = s[left:right + 1]
                if best == "" or len(candidate) < len(best):
                    best = candidate
                break

    return best

⚡ Approach 3: Sliding Window With Counts (Best)

The idea in one line: keep one window, grow it on the right until valid, then shrink it on the left to the smallest valid size.

The idea:

Count what t needs in a table.
Track missing, the number of needed letters the window still lacks.
Missing starts at the length of t.

How it works:

Move the right edge forward and add each letter.
If that letter was still needed, drop missing by one.
When missing hits zero, the window holds everything.
Now shrink from the left while the window stays valid, recording the smallest.

Why it is fast:

Each letter enters once and leaves once.
One smooth grow-and-shrink pass, so the time is O(n).

Here is the window growing until it is complete, then shrinking to the smallest valid size.

Steps to Solve

Count every letter that t needs. Set missing to the length of t.
Move the right edge across s. Add each letter and if it was needed, lower missing.
When missing is zero, the window holds everything t needs.
Shrink from the left while the window stays complete, and record the smallest window seen.
When you remove a needed letter from the left, raise missing so the window grows again.
At the end, return the smallest window you recorded, or an empty string if none worked.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a dictionary for the needed counts and a missing counter to know when the window covers t.

def min_window(s, t):
    need = {}                     # how many of each letter t needs
    for c in t:
        need[c] = need.get(c, 0) + 1

    missing = len(t)              # needed letters not yet covered
    left = 0
    best = ""                     # smallest valid window found
    best_len = len(s) + 1         # length of that window
    for right in range(len(s)):
        if need.get(s[right], 0) > 0:   # this letter was still needed
            missing -= 1                # one fewer letter missing
        need[s[right]] = need.get(s[right], 0) - 1  # count it
        while missing == 0:             # window has everything
            if right - left + 1 < best_len:   # smaller window
                best_len = right - left + 1
                best = s[left:right + 1]
            need[s[left]] += 1          # give back the left letter
            if need[s[left]] > 0:       # now that letter is needed again
                missing += 1
            left += 1                   # shrink from the left
    return best


s = "ADOBECODEBANC"
t = "ABC"
print(min_window(s, t))

The output of the above code will be:

BANC

Let us walk through the Python version line by line and see why each line is there.

need = {} then the loop fills it. This dictionary holds each letter t needs and how many of it. So for "ABC" it becomes one A, one B, one C.

missing = len(t) is how many needed letters the window still lacks. It starts at the full length of t because the window is empty.

left = 0 is the left edge. best = "" keeps the smallest valid window. best_len = len(s) + 1 starts bigger than any real window, so the first valid window always replaces it.

for right in range(len(s)): moves the right edge across s. Each loop pulls in one new letter.

if need.get(s[right], 0) > 0: checks if the new letter was still needed. A positive count means yes. Then missing -= 1 marks one fewer letter missing.

need[s[right]] = need.get(s[right], 0) - 1 lowers the count for that letter. Letters not in t go negative, which is fine. That just means the window has extra of them.

while missing == 0: runs when the window holds everything t needs. Inside, we first try to record a smaller window. if right - left + 1 < best_len: checks the size and stores it if it is the smallest so far.

need[s[left]] += 1 gives back the leftmost letter as we remove it. if need[s[left]] > 0: checks if that letter was a needed one. If its count goes positive, the window now lacks it, so missing += 1. Then left += 1 shrinks the window.

return best gives back the smallest valid window, or an empty string if none was found.

⏱️ Time and Space Complexity

The brute force checks every window from scratch, so it is slow at O(n²) or worse. The sliding window grows and shrinks one window and touches each letter at most twice. So it runs in O(n) time. The memory holds the counts for the letters of t, which is small.

Approach	Time Complexity	Space Complexity
Check every substring (brute force)	O(n² · k)	O(k)
Expand from each start (better)	O(n²)	O(k)
Sliding window with counts (best)	O(n)	O(k)

Tip

Here k is the number of different letters in t. The counts table never grows past that, so the memory stays small even for long strings.

🧩 Key Takeaways

✅ Grow the window on the right until it holds every letter t needs.
✅ Then shrink it on the left to make it as small as possible while it stays complete.
✅ The missing counter tells you in one step when the window has everything.
✅ Each letter enters once and leaves once, so the whole thing runs in O(n).
✅ Say the brute force first, then explain the grow-then-shrink window. That shows your thinking.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Longest Repeating Character Replacement Next Permutation in String

Minimum Window Substring

Follow Us

Follow Us