Minimum Window Substring

Problem

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string.

Examples

The brute-force approach

Try every substring of s. For each, check if it contains all characters of t. Track the shortest valid one.

best = ""
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if has_all(s[i:j], t):
            if not best or j-i < len(best):
                best = s[i:j]
return best

O(n²×|t|) — all substrings plus a check per substring.

Spotting the pattern

This is a Sliding Window problem. The key question to ask yourself:

How does the "formed" counter let you know exactly when the window is valid without re-scanning the entire window each time the right pointer moves?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.