Sign in
Skip to solution
hardDSA

How do you find the minimum window substring?

932 views
01

Understand the problem

Explain minimum window covering all chars.

stringssliding-window
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Use a variable sliding window with a need-count map of the target characters. Expand right until the window covers all needs, then shrink left while still valid, recording the smallest. Each character enters and leaves once — O(n + m).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Expand then shrink
Run Playground
from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    required = len(need)
    formed = 0
    window = {}
    best = (float('inf'), 0, 0)
    left = 0
    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            formed += 1
        while formed == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            lc = s[left]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                formed -= 1
            left += 1
    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]


# --- demo ---
print(min_window("ADOBECODEBANC", "ABC"))   # BANC
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 106 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track