Minimum Window Substring

Hard

The problem

Given strings s and t, find the shortest piece of s (letters next to each other) that contains every letter of t, counting repeats (if t has two a's, the piece needs at least two a's). Return that piece, or an empty string "" if there is none.

Example 1
Input: s = "xaybzcab", t = "abc"
Output: "cab"
The piece "cab" at the end has an a, a b and a c, and it is only 3 long. No piece can be shorter than t itself.
Example 2
Input: s = "a", t = "aa"
Output: ""
t needs two a's but s has only one.

Limits

1 ≤ s.length, t.length ≤ 100,000
s and t contain only letters
If an answer exists, the shortest piece is unique

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Track how many required letters are still missing. The window is valid at exactly zero missing.

The idea

Expand right until the window covers t; then shrink left as far as it stays valid, recording the smallest window each time.

Target: O(n + m) time

Go function shape

func minWindow(s string, t string) string

Reference solution

Tested with go test. Try it yourself first, then compare.

// MinWindow: smallest substring of s containing every char of t (with multiplicity).
func MinWindow(s, t string) string {
	if len(t) == 0 || len(t) > len(s) {
		return ""
	}
	need := [128]int{}
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	missing := len(t) // how many required chars the window still lacks
	bestStart, bestLen, left := 0, len(s)+1, 0
	for right := 0; right < len(s); right++ {
		if need[s[right]] > 0 {
			missing--
		}
		need[s[right]]--
		for missing == 0 { // window is valid: try to shrink it
			if right-left+1 < bestLen {
				bestStart, bestLen = left, right-left+1
			}
			need[s[left]]++
			if need[s[left]] > 0 {
				missing++
			}
			left++
		}
	}
	if bestLen > len(s) {
		return ""
	}
	return s[bestStart : bestStart+bestLen]
}

Read the lesson: Sliding Window