-
Notifications
You must be signed in to change notification settings - Fork 0
049 — Minimum Window Substring
LeetCode 76 · Hard. Given two strings s and t, return the shortest substring of s that contains every character of t (including duplicates — if t has two 'a's, the substring needs at least two 'a's too). Return "" if no such substring exists.
Imagine you're walking down a grocery aisle with a shopping list (t, possibly with duplicate items — "2 apples, 1 banana"), and you want the shortest continuous stretch of shelf (s) that contains everything on your list. You walk forward, grabbing items into your basket one shelf-slot at a time. The moment your basket satisfies the entire list, you have a valid stretch — but it might not be the shortest one that ends nearby. So you start trimming from the back of your stretch, dropping items one at a time, for as long as the basket still satisfies the list. The instant trimming would break the list requirement, you stop, record how short this stretch got, and keep walking forward to look for the next valid stretch.
That's expand-until-valid, then contract-while-still-valid — the mirror image of the "expand, then contract only when invalid" shape from earlier Sliding Window problems.
"Shortest substring... containing all characters of t" is contiguous + minimize, with a multiset-matching constraint ("contains every character of t, counts included"). Whenever a sliding window problem's target is shortest rather than longest, the shape flips: expand right until the window first becomes valid, then greedily contract left for as long as it stays valid, recording the window length at every valid point along the way, rather than only contracting to restore validity after breaking it.
For each starting index, extend the window forward until it first contains every character of t with the required counts, then stop — that's the shortest valid window for that particular start.
private func satisfies(_ window: [Character: Int], _ required: [Character: Int]) -> Bool {
for (char, count) in required {
if (window[char] ?? 0) < count {
return false
}
}
return true
}
func minWindowBruteForce(_ s: String, _ t: String) -> String {
let sChars = Array(s)
let tChars = Array(t)
guard !sChars.isEmpty, !tChars.isEmpty, tChars.count <= sChars.count else { return "" }
var required: [Character: Int] = [:]
for c in tChars {
required[c, default: 0] += 1
}
var bestStart = -1
var bestLength = Int.max
for start in 0..<sChars.count {
var window: [Character: Int] = [:]
for end in start..<sChars.count {
window[sChars[end], default: 0] += 1
let length = end - start + 1
if length < bestLength && satisfies(window, required) {
bestLength = length
bestStart = start
break // shortest valid window starting at `start` — move to the next start
}
}
}
guard bestStart != -1 else { return "" }
return String(sChars[bestStart..<(bestStart + bestLength)])
}Big-O: O(n²) time in the worst case — up to n starting points, each scanning forward up to n characters, with an O(|t| unique) (effectively constant) satisfies check at each step. O(|t|) extra space for the frequency maps.
Slide a window with expand/contract, but track validity with a single integer counter (have vs. need) instead of re-checking the whole requirement map at every step.
func minWindow(_ s: String, _ t: String) -> String {
let sChars = Array(s)
let tChars = Array(t)
guard !sChars.isEmpty, !tChars.isEmpty, tChars.count <= sChars.count else { return "" }
var required: [Character: Int] = [:]
for c in tChars {
required[c, default: 0] += 1
}
let need = required.count // number of DISTINCT characters that must be fully satisfied
var windowCounts: [Character: Int] = [:]
var have = 0
var left = 0
var bestStart = -1
var bestLength = Int.max
for right in 0..<sChars.count {
let c = sChars[right]
windowCounts[c, default: 0] += 1
if let req = required[c], windowCounts[c] == req {
have += 1
}
while have == need {
let length = right - left + 1
if length < bestLength {
bestLength = length
bestStart = left
}
let leftChar = sChars[left]
windowCounts[leftChar]! -= 1
if let req = required[leftChar], windowCounts[leftChar]! < req {
have -= 1
}
left += 1
}
}
guard bestStart != -1 else { return "" }
return String(sChars[bestStart..<(bestStart + bestLength)])
}
// smoke test
print(minWindow("ADOBECODEBANC", "ABC")) // "BANC"
print(minWindow("a", "a")) // "a"
print(minWindow("a", "aa")) // ""Big-O: O(n + m) time, where n = s.count and m = t.count — right advances n times total, left advances at most n times total, and each step does O(1) work (a dictionary update plus a comparison). O(m) extra space for the requirement and window maps.
The brute force asks "does this window satisfy the requirement?" by re-scanning the entire requirement map from scratch at every single character added — satisfies() runs on every step. The optimal solution replaces that repeated full-map check with a single integer, have, that only changes when a specific character's count crosses its exact required threshold — going from "not enough of this character" to "exactly enough," or vice versa during contraction. Checking have == need is O(1), versus re-verifying every entry in required every time. That's what turns an O(|t|)-per-step check into an O(1)-per-step check, and lets left greedily contract as far as validity allows without ever needing to "look back" at the full requirement map.
- Sliding Window — the expand-until-valid, then contract-while-valid variant of the window skeleton.
- Arrays & Strings — the string being scanned.
-
Hash Maps & Hash Sets — the
required/windowCountsmaps, and thehave/needtrick that avoids re-scanning them.
Minimum Window Substring is grocery shopping against a list — expand the basket until every item is covered, then trim from the back for as long as the list still checks out, remembering the shortest stretch that ever worked.
The have counter increments only when windowCounts[c] == req — using ==, not >=. Explain why using == here is essential for correctness: what would go wrong if a character's count kept climbing well past its required amount (for example, t needs one 'a' but the window has collected five)?
⬅️ Previous: Permutation in String · Next: Sliding Window Maximum ➡️