Coding problem · Hard · Sliding Window
Minimum Window Substring
Hard Algorithms & data structures Seen at Meta, Amazon, Airbnb, LinkedIn
Given strings s and t, return the minimum window substring of s that contains every character of t (including duplicates). If there is no such window, return "". The answer is unique.
Example 1
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC"
Example 2
Input: s = "a", t = "aa" Output: ""
Constraints
1 <= s.length, t.length <= 10^5
Hints
Hint 1
Expand right until the window covers t, then shrink left while it still covers it.
Hint 2
Track how many required characters are currently satisfied instead of re-checking the whole map.
Write and run your solution
Loading the editor… (JavaScript is required to run code in your browser.)
Solution and explanation
Show the solution
Time O(|s| + |t|) · Space O(alphabet)
Count what t needs. Move right forward, decrementing needs; when a need reaches zero, one more character is satisfied. Once all are satisfied, record the window and move left forward, giving characters back, until the window stops being valid. Every index enters and leaves the window once: O(|s| + |t|).
Reference solution
function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
let missing = need.size, left = 0, best = [0, Infinity];
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (need.has(c)) {
need.set(c, need.get(c) - 1);
if (need.get(c) === 0) missing--;
}
while (missing === 0) {
if (right - left < best[1] - best[0]) best = [left, right];
const d = s[left++];
if (need.has(d)) {
need.set(d, need.get(d) + 1);
if (need.get(d) > 0) missing++;
}
}
}
return best[1] === Infinity ? "" : s.slice(best[0], best[1] + 1);
}
function minWindow(s: string, t: string): string {
const need = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
let missing = need.size, left = 0;
let best: [number, number] = [0, Infinity];
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (need.has(c)) {
need.set(c, need.get(c)! - 1);
if (need.get(c) === 0) missing--;
}
while (missing === 0) {
if (right - left < best[1] - best[0]) best = [left, right];
const d = s[left++];
if (need.has(d)) {
need.set(d, need.get(d)! + 1);
if (need.get(d)! > 0) missing++;
}
}
}
return best[1] === Infinity ? "" : s.slice(best[0], best[1] + 1);
}
from collections import Counter
def min_window(s: str, t: str) -> str:
need = Counter(t)
missing = len(need)
left = 0
best = (0, float("inf"))
for right, c in enumerate(s):
if c in need:
need[c] -= 1
if need[c] == 0:
missing -= 1
while missing == 0:
if right - left < best[1] - best[0]:
best = (left, right)
d = s[left]
left += 1
if d in need:
need[d] += 1
if need[d] > 0:
missing += 1
return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]
<?php
function minWindow(string $s, string $t): string
{
$need = count_chars($t, 1);
$missing = count($need);
$left = 0;
$bestStart = 0;
$bestLen = PHP_INT_MAX;
for ($right = 0, $n = strlen($s); $right < $n; $right++) {
$c = ord($s[$right]);
if (isset($need[$c]) && --$need[$c] === 0) {
$missing--;
}
while ($missing === 0) {
if ($right - $left + 1 < $bestLen) {
[$bestStart, $bestLen] = [$left, $right - $left + 1];
}
$d = ord($s[$left++]);
if (isset($need[$d]) && ++$need[$d] > 0) {
$missing++;
}
}
}
return $bestLen === PHP_INT_MAX ? '' : substr($s, $bestStart, $bestLen);
}
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
int missing = 0;
for (char c : t.toCharArray()) if (need[c]++ == 0) missing++;
int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
if (--need[s.charAt(right)] == 0) missing--;
while (missing == 0) {
if (right - left + 1 < bestLen) { bestStart = left; bestLen = right - left + 1; }
if (++need[s.charAt(left++)] > 0) missing++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
}