Minimum Window Substring
Problem statement
You're given two strings, s and t. Find the shortest contiguous piece of s — a substring — that contains every character in t, including repeats. For example, if t has two 'a's, the window has to contain at least two 'a's somewhere inside it, not just one.
Return that shortest window as a string. If no window of s contains everything t needs, return an empty string instead. It's guaranteed that whenever an answer exists, there's only one shortest window (no ties to break).
Examples
Example 1
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" is the shortest substring of s that contains at least one 'A', one 'B' and one 'C'.
Example 2
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is already the shortest (and only) window that contains everything t needs.
Example 3
Input: s = "a", t = "aa"
Output: ""
Explanation: t needs two 'a's, but s only has one character total, so no window of s can ever satisfy the requirement.
Hints
Approach
Optimal: Sliding window with two pointers
Intuition
The brute force approach restarts its window from scratch at every starting index, throwing away all the counting work it just did the moment it moves to the next one. A window whose left and right edges only ever move forward — never backward, and never reset — avoids that waste: expand the right edge until the window contains everything t needs, then shrink the left edge as far as possible while the window stays valid, recording the window's length each time it's still valid. Because both edges only move forward, the whole string is scanned just once in total, not once per starting index.
Instead of checking "does every character have enough count?" from scratch every time, keep a single running counter: formed, the number of distinct characters in t whose required count is currently met inside the window. The window is valid exactly when formed equals the number of distinct characters t needs — a single number comparison, not a full re-check of every character.
Steps
- Count how many of each character
trequires (need), and note how many distinct characters that is (required). - Keep a running count of characters currently in the window (
windowCount), and a counterformedfor how many distinct required characters are currently fully satisfied. - Move the right edge forward one character at a time: add that character to
windowCount, and if its count just reached exactly what's needed, incrementformed. - Whenever
formed == required(the window is currently valid), repeatedly try shrinking from the left: record the window's length if it's the best seen so far, then remove the leftmost character fromwindowCountand move the left edge forward — decrementingformedif that removal just made some character's count fall below what's needed. - Once the right edge has scanned the whole string, return the shortest valid window recorded, or an empty string if none was found.
Dry run
s = "ADOBECODEBANC", t = "ABC" (need = {A:1, B:1, C:1}, required = 3)
| right reaches | window | formed | shrinking? | best window so far |
|---|---|---|---|---|
| index 5 ('C') | "ADOBEC" | 3 (valid) | shrink left from 0 → 4 (loses 'A') | "ADOBEC" (len 6) |
| index 9 ('B') | "CODEB" then extends | building back toward 3 | — | "ADOBEC" (len 6) |
| index 12 ('C') | "BANC" | 3 (valid) | shrink left, window stays "BANC" | "BANC" (len 4) |
The window "BANC" is found once the right edge reaches the final 'C', and shrinking from the left can't make it any smaller without losing a required character, so it becomes the final answer — matching the expected output, and matching what the brute force approach found, but without ever restarting the scan.
Edge cases: when s = "a", t = "aa", formed can never reach required (there's only one 'a' available but two are needed), so the window is never valid and an empty string is correctly returned. Because both left and right only ever move forward, the total work is proportional to the combined length of s and t, not to the length of s squared.
Complexity
Time O(m + n) - building the required counts from t is O(n), and the right and left pointers each move forward at most m times total across the whole scan of s, with O(1) work at each step, giving a combined O(m + n). This matches the O(m + n) bound the problem's own follow-up asks for.
Space O(n) - the need and windowCount maps both scale with the number of distinct characters involved, not with the length of s.
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ""
need = Counter(t)
required = len(need) # number of distinct characters that must be satisfied
window_count = Counter()
formed = 0 # number of distinct characters currently satisfied
best_len = float("inf")
best_left = 0
left = 0
for right, char in enumerate(s):
window_count[char] += 1
if char in need and window_count[char] == need[char]:
formed += 1
while formed == required:
if right - left + 1 < best_len:
best_len = right - left + 1
best_left = left
left_char = s[left]
window_count[left_char] -= 1
if left_char in need and window_count[left_char] < need[left_char]:
formed -= 1
left += 1
return "" if best_len == float("inf") else s[best_left:best_left + best_len]
if __name__ == "__main__":
print(Solution().minWindow("ADOBECODEBANC", "ABC")) # "BANC"
print(Solution().minWindow("a", "a")) # "a"
print(Solution().minWindow("a", "aa")) # ""RecapThe whole problem in a few lines, for the night before
- Spot it: "shortest/smallest window containing all of X" (with duplicates counted) inside a longer string
- Idea: sliding window with two pointers — expand right until the window is valid, then shrink left as far as possible while it stays valid, tracking a single
formedcounter instead of re-checking every character - Cost: O(m + n) time, O(n) space (trying every starting index fresh is O(m^2 · n))
- Trap: resetting the window's character counts back to empty for every new starting index instead of letting left and right both only move forward — that's what turns an O(m + n) scan back into an O(m^2) one
Interview follow-ups
What if s and t could contain a much larger character set, such as full Unicode, instead of just English letters?
The same sliding window logic applies unchanged — only the choice of data structure for need and windowCount would need to switch from something sized for a fixed small alphabet (like a 128-entry array) to a general hash map, since the character set is no longer small and bounded.
What if you needed to return every minimal window of this length, not just one?
Once the single shortest length is known from a first pass, run the sliding window logic again (or track matches during the same pass) and record every window whose length equals that shortest length, rather than only ever keeping a single best answer.
Frequently asked questions
Moving right forward is how new characters ever get considered, and moving left forward is how a window that's already valid gets tested to see if it can be made smaller — neither pointer ever benefits from revisiting territory it has already passed, since a substring is uniquely defined by its left and right positions moving in one direction. That's exactly why the whole string only needs to be scanned once.
Checking every character in need on every step would cost time proportional to the number of distinct characters in t, on top of the work already being done — for a t with many distinct characters, that adds up. Tracking a single count of how many characters are currently satisfied turns that repeated check into one quick number comparison instead.
Finding the smallest contiguous window of log lines, requests, or events that contains a required set of markers — every error code in a checklist, say — is a direct real-world version of this exact search, and the shrink-while-valid sliding window technique is the standard efficient tool for it.
Only the counts matter — the window just needs to contain at least as many of each required character as t has, wherever they happen to sit inside the window. This is why the solution counts characters in t rather than trying to match t as a contiguous or ordered pattern.