Minimum Window Substring

Given two strings s and t, return the smallest substring of s that contains all characters of t (including duplicates). If no such substring exists, return the empty string.

A brute force check of all substrings is too slow. A sliding window with character counts solves it in O(n).

Function signature

func MinWindow(s string, t string) string

Inputs / outputs

• s: source string.
• t: target string (may contain duplicates).
• Return: the minimum window substring, or "" if none.

Example

s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Constraints

• 0 <= len(s), len(t) <= 100_000

Core idea (near-solution)

Use a sliding window with counts:

• need[c]: how many of character c you still need.
• formed: how many distinct characters have been satisfied.
• required: number of distinct characters in t.

Invariant: when formed == required, the current window contains all required characters (including duplicates). Then shrink from the left to minimize it.

Algorithm (step-by-step)

1. Build a count map for t and set required to the number of distinct chars.
2. Initialize l = 0, formed = 0, and a map window.
3. Expand r from 0 to len(s)-1:
   • Add s[r] to window.
   • If a character count matches t, increment formed.
   • While formed == required:
     • Update best window if this one is smaller.
     • Remove s[l] from window and increment l.
     • If a required count falls below the needed amount, decrement formed.
4. Return the best window found or "".

Correctness sketch

• Invariant: when formed == required, the current window contains all required characters (including duplicates). Then shrink from the left to minimize it.
• The window state exactly matches the elements in s[l..r].
• Shrinking/expanding preserves validity, so any recorded window is correct.
• The best recorded window is optimal because all candidate windows are considered.

Trace (hand walkthrough)

Example input:
s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Walk:
- expand to r=5 -> window "ADOBEC" covers A,B,C (best=6)
- shrink l to 1 loses A, keep expanding to r=10 (A) then to r=12 (C)
- shrink l to 9 -> window "BANC" still covers (best=4)

Pitfalls to avoid

• Ignoring duplicate counts in t (must match multiplicities).
• Shrinking before verifying the window is valid.

Complexity

• Time: O(n)
• Extra space: O(k) where k is the alphabet size.

Implementation notes (Go)

• Track counts for target characters and a formed counter.
• Shrink while valid to minimize length; record best window indices.