Lesson 14 — Sliding Window III: Minimum Window

~25 minutes · sliding window validity · Python

Tonight's hard problem is Minimum Window Substring. Interviewers like it because the brute force idea is obvious, but the clean solution depends on saying one sentence exactly: what makes the current window valid?

The invariant

Expand until the window covers every needed character count, then shrink to find the smallest such window. (Hard — go slow.)

That's the whole lesson. A sliding window is just two pointers around a slice of the string. The right pointer grows the window until it becomes useful; the left pointer shrinks it while it stays useful. For this problem, useful means: every character in t appears inside the window with enough count.

The window grows until it covers the required counts, then shrinks from the left to test smaller valid answers.

Minimum Window: the slow way first

The problem gives two strings, s and t, and asks for the smallest substring of s containing all characters of t, including duplicates. The brute force approach is: try every substring, count its characters, and keep the shortest substring that covers t. That is O(n³) if you recount each substring from scratch, so it collapses quickly.

The better approach keeps one live count structure as the window moves. Python's Counter is a dictionary subclass for counting hashable objects, which is exactly what character counts are. The LeetCode statement is here; the only extra Python tool below is Counter.

Minimum Window: the window way

Put from collections import Counter at the top of your solution. Read missing as: how many required characters are still owed, counting duplicates. When missing == 0, the window is valid. Then the inner loop shrinks from the left, recording every valid candidate before it breaks validity.

def min_window(s, t):
    need = Counter(t); best = (float("inf"), 0, 0)  # length, left, right
    missing = len(t); left = 0                      # chars still owed
    for right, ch in enumerate(s):                  # expand right
        if need[ch] > 0: missing -= 1               # paid one owed char
        need[ch] -= 1
        while missing == 0:                         # valid: try shrinking
            if right - left + 1 < best[0]: best = (right - left + 1, left, right + 1)
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1      # removed a needed char
            left += 1
    return s[best[1]:best[2]]

The hard part is emotional, not mechanical: trust the invariant. Expand until valid. Once valid, shrink until removing one more character would make it invalid. Every time the window is valid, it is a candidate answer.

Transfer: same pattern, new costume

A monitoring system stores event codes as a string. Given events = "AXYBCAZ" and required codes "ABC", return the shortest contiguous segment containing all required codes. Before opening the reveal: name the validity rule, then say when the left pointer moves.

What the trade buys you

Here n = len(s), m = len(t), and k is the number of distinct characters the counters track. The important interview sentence is simpler: each pointer only moves forward, so the scan is linear.

Practice — answer before you scroll past

while missing == 0:
    if right - left + 1 < best[0]:
        best = (right - left + 1, left, right + 1)
    need[s[left]] += 1
    left += 1

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Minimum Window Substring — in the predict step, say the brute force and the validity rule before writing code. In the encode step, write the invariant from this page in your own words.

This is the sliding-window self-check gate: state the validity rule from memory before touching the keyboard.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.