How do you find the minimum window substring? | Interview Question

Q: How do you find the minimum window substring?

**Target Audience:** Intermediate candidates — you should know strings, maps and the basic sliding window idea; every term is still defined here. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged `📌 Interview term:` with the exact vocabulary an interviewer expects. Every output quoted in the **Verified** section was printed by actually running the code shown with `python3`. ## 1. Why This Even Matters — A Story First You have a shopping list — one apple, one banana, one carrot — and a long market street where stalls sell one item each, in a fixed order. You want the **shortest stretch of consecutive stalls** where you can buy everything on your list. You walk forward, adding stalls to your stretch until you have everything. Then you try to drop stalls from the back of your stretch while you still have everything, because a shorter stretch is better. When dropping one more would lose something you nee

The problem

Question presented to candidate: "Given two strings s and t, return the smallest substring of s that contains every character of t, including duplicates. If there is none, return an empty string. For s = 'ADOBECODEBANC' and t = 'ABC' the answer is 'BANC'. Please solve it in Python in linear time."

What a strong answer should cover:

Brute force over all substrings is at least O(n²); the expected answer is a variable-size sliding window: expand right until valid, shrink left while valid, O(|s| + |t|).
Frequency maps for t (need) and the window, because duplicates in t matter.
An O(1) validity check with need/have counters: have changes only when a count crosses its threshold.
Recording the answer inside the shrink loop, the leftmost-on-ties rule, and the no-window case.
Python specifics: collections.Counter(t) builds the need map in one line and returns 0 for missing keys; float("inf") as the 'no window yet' length; slice once at the end.

Clarifying questions expected:

"Do duplicate characters in t have to appear that many times?"
"What do I return if no window exists, or if t is empty?"

Code / implementation expected: Yes — a min_window(s, t) function in Python with expand/shrink and need/have counters.

strings
sliding-window

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Intermediate candidates — you should know strings, maps and the basic sliding window idea; every term is still defined here. Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged 📌 Interview term: with the exact vocabulary an interviewer expects. Every output quoted in the Verified section was printed by actually running the code shown with python3.

1. Why This Even Matters — A Story First

You have a shopping list — one apple, one banana, one carrot — and a long market street where stalls sell one item each, in a fixed order. You want the shortest stretch of consecutive stalls where you can buy everything on your list. You walk forward, adding stalls to your stretch until you have everything. Then you try to drop stalls from the back of your stretch while you still have

The solution is hidden so you can try first

7 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonMinimum window substring on eight inputs

Practice

PythonBrute force vs sliding window: same answers, far fewer steps

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.