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 "".
Example 1:
Input:s = "ADOBECODEBANC", t = "ABC"
Output:"BANC"
The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input:s = "a", t = "a"
Output:"a"
The entire string s is the minimum window.
Example 3:
Input:s = "a", t = "aa"
Output:""
Both 'a's from t must be included but s only has one 'a'.
Constraints:
m == s.length, n == t.length
1 ≤ m, n ≤ 10⁵
s and t consist of uppercase and lowercase English letters.
Hints
Hint 1Use two pointers and expand the right side of the window.▼
Move the right pointer to include more characters. Track how many distinct required characters from t are fully satisfied in the current window.
Hint 2Once you have all required chars, try to shrink from the left.▼
When have == need, the current window is valid. Record its length as a candidate answer and then advance l to try to find a shorter valid window.
Hint 3Use a hash map to count required characters vs current window counts.▼
countT maps each char in t to how many times it's needed. window tracks how many times each char appears in the current window. A char c is "satisfied" when window[c] ≥ countT[c].
🌐 Real-World Analogy
DNA Sequence Analysis
Genomics tools scan long DNA sequences to find the shortest contiguous region containing all target gene markers. The sliding window approach lets researchers move through millions of base pairs in O(n) time — expanding to find all markers, then shrinking to minimize the region. This is far more efficient than checking every possible substring, making it foundational in bioinformatics pipelines.
Optimal Approach — Sliding Window + Hash Map
O(n) Time
🪟
Expand R, Shrink L — Track have / need
Time O(n)Space O(k)
We use two pointers L and R. R expands the window to include characters; L shrinks it once all required chars are satisfied. We track have (satisfied distinct chars) vs need (total distinct chars in t).
1Build countT from t. need = len(countT), have = 0.
2Expand R: add s[r] to window. If window[c] == countT[c], increment have.
3While have == need: update best window, then shrink L (remove s[l], decrement have if needed).
4Return the best window substring found.
Each character is added and removed at most once from the window, giving O(n + m) time and O(k) space for the hash maps, where k is the character set size.
Target T — Required Characters
String S — Sliding Window
have / need—
READY—
Press ▶ or step forward to begin.
L—
R—
have—
need—
best—
✓
—
Space Play/Pause·←→ Step·R Reset
Executing Code
defminWindow(s, t):
countT, window = Counter(t), {}
have, need = 0, len(countT)
res, resLen = [-1,-1], float("infinity")
l = 0
for r inrange(len(s)):
c = s[r]; window[c] = window.get(c,0)+1
if c in countT and window[c]==countT[c]: have+=1
while have == need:
if (r-l+1) < resLen: res=[l,r]; resLen=r-l+1
window[s[l]] -= 1
if s[l] in countT and window[s[l]]<countT[s[l]]: have-=1
l += 1
return s[res[0]:res[1]+1] if resLen!=float("infinity") else""
Discussion
…