076. Minimum Window Substring

At a Glance

• Topic: sliding-window
• Pattern: Sliding Window (variable window + need/have)
• Difficulty: Hard
• Companies: Google, Amazon, Meta, Microsoft, Uber
• Frequency: Very High
• LeetCode: 76

Problem (one-liner)

Given strings source and pattern, return the lexicographically not required but shortest contiguous substring of source that contains all characters of pattern with at least the same multiplicities. If none, return "".

Recognition Cues

• "Shortest substring containing all characters of another string"
• Multiplicity matters — not just set membership
• Classic need / formed / required or have / need window validity

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — every (left, right) window, rescan pattern counts — O(n² · m) time; only a starting point.
• Better — expand right, maintain character counts, check validity on each step without formed — still O(n · |Σ|) work per shrink in naive form.
• Acceptable — two maps / array buckets for need and have, update formed only when a character crosses its saturation threshold — O(n) passes over source with O(|Σ|) space.
• Optimal — same window, but shrink left while formed == required to pin the shortest valid window ending at right — O(n) time for fixed alphabet; interview default.

Optimal Solution

Go

func minWindow(source string, pattern string) string {
	need := make(map[byte]int)
	for index := 0; index < len(pattern); index++ {
		need[pattern[index]]++
	}
	required := len(need)
	formed := 0
	have := make(map[byte]int)
	leftPointer := 0
	bestLeft, bestRight := -1, -1
	bestLength := len(source) + 1

	for rightPointer := 0; rightPointer < len(source); rightPointer++ {
		character := source[rightPointer]
		have[character]++
		if need[character] > 0 && have[character] == need[character] {
			formed++
		}
		for formed == required && leftPointer <= rightPointer {
			windowLen := rightPointer - leftPointer + 1
			if windowLen < bestLength {
				bestLength = windowLen
				bestLeft = leftPointer
				bestRight = rightPointer
			}
			leftChar := source[leftPointer]
			have[leftChar]--
			if need[leftChar] > 0 && have[leftChar] < need[leftChar] {
				formed--
			}
			leftPointer++
		}
	}
	if bestLeft == -1 {
		return ""
	}
	return source[bestLeft : bestRight+1]
}

JavaScript

function minWindow(source, pattern) {
	const need = new Map();
	for (const patternCharacter of pattern) {
		need.set(patternCharacter, (need.get(patternCharacter) || 0) + 1);
	}
	const required = need.size;
	let formed = 0;
	const have = new Map();
	let leftPointer = 0;
	let bestLeft = -1;
	let bestRight = -1;
	let bestLength = source.length + 1;

	for (let rightPointer = 0; rightPointer < source.length; rightPointer++) {
		const character = source[rightPointer];
		have.set(character, (have.get(character) || 0) + 1);
		if (need.has(character) && have.get(character) === need.get(character)) {
			formed++;
		}
		while (formed === required && leftPointer <= rightPointer) {
			const windowLen = rightPointer - leftPointer + 1;
			if (windowLen < bestLength) {
				bestLength = windowLen;
				bestLeft = leftPointer;
				bestRight = rightPointer;
			}
			const leftChar = source[leftPointer];
			have.set(leftChar, have.get(leftChar) - 1);
			if (need.has(leftChar) && have.get(leftChar) < need.get(leftChar)) {
				formed--;
			}
			leftPointer++;
		}
	}
	if (bestLeft === -1) {
		return "";
	}
	return source.slice(bestLeft, bestRight + 1);
}

Walkthrough

source = "ADOBECODEBANC", pattern = "ABC"

Invariant: when formed == required, the window is valid; inner while tries shortest valid window ending at rightPointer.

Edge Cases

• pattern longer than source → ""
• pattern == "" (LeetCode defines as "" return — clarify with interviewer)
• All chars same, pattern "AAA" and source many As
• Unicode / ASCII — problem is byte-oriented on LC for Go; JS strings are UTF-16 (surrogate pairs rare in interviews)

Pitfalls

• Counting required as len(pattern) instead of distinct keys with satisfied multiplicity
• Using map size for formed — must increment/decrement only when crossing threshold have[ch]==need[ch]
• Returning substring indices off-by-one

Similar Problems

• 3. Longest Substring Without Repeating Characters — variable window; distinct chars (Medium stepping stone).
• 567. Permutation in String — fixed multiset match (Medium).
• 30. Substring with Concatenation of All Words — Hard sibling: window over word-multiset.

Variants

• Minimum window covering k distinct integers — same skeleton with distinct-count validity.
• At most one substitution / insert allowed — add state or two-phase window.
• Streaming infinite stream — cannot globally minimize length without bound; ask if window is bounded.

Mind-Map Tags

#sliding-window #minimum-window #need-have #formed #two-map #hard-string