Minimum Window Substring

Problem

Given strings s and t, return the smallest substring of s that contains every character of t including duplicates. If no such window exists, return the empty string.

Example

s = "ADOBECODEBANC", t = "ABC"  ->  "BANC"

Go Solution

package main

import "fmt"

func minWindow(s, t string) string {
    if t == "" || len(s) < len(t) {
        return ""
    }
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    missing := len(t) // chars still needed inside the window
    left, start, end := 0, 0, 0 // best window = s[start:end]

    for right := 0; right < len(s); right++ {
        if need[s[right]] > 0 {
            missing--
        }
        need[s[right]]--
        for missing == 0 { // window is valid: shrink from the left
            if end == 0 || right-left+1 < end-start {
                start, end = left, right+1
            }
            need[s[left]]++
            if need[s[left]] > 0 {
                missing++
            }
            left++
        }
    }
    return s[start:end]
}

func main() {
    fmt.Println(minWindow("ADOBECODEBANC", "ABC")) // BANC
}

How to Solve

1. Count what t requires. need[c] starts as how many of each character the window must contain; missing is the total still owed.
2. Grow the window with right. Decrement need[c] for each new character; if it was still positive (genuinely needed), decrement missing. Characters not in t simply go negative and never affect missing.
3. When missing == 0, the window is valid — shrink it. Record it if it's the smallest so far, then advance left, restoring need; if a count climbs back above zero, the window is short a character again, so bump missing and stop shrinking.
4. end == 0 as the “no window yet” sentinel — a real window always sets end = right + 1 > 0, so an untouched end returns s[0:0], the empty string.

Complexity

Time: O(|s| + |t|) — each character of s enters and leaves the window once. Space: O(|t|) for the counts (O(unique chars)).