# Minimum Window Substring

- **Canonical ID**: `minimum-window-substring`
- **Canonical URL**: https://dsacheatsheet.com/problems/minimum-window-substring
- **Difficulty**: hard
- **Patterns**: Sliding Window
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/minimum-window-substring/

## 1. Core Invariant / The Trick

Maintain `have == need` count of distinct required characters from `t`. Expand `r` until `have == need`, then advance `l` aggressively while maintaining `have == need` and updating the smallest slice.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(|S| + |T|)`
- **Space Complexity**: `O(|T|)`
- **Proof**: Both `l` and `r` advance across `s` strictly monotonically at most once each.

## 3. Minimal Idiomatic Code

### Python
```python
def minWindow(s: str, t: str) -> str:
    if not t: return ""
    need = Counter(t)
    window = {}
    have, req = 0, len(need)
    res_l, res_len = 0, float('inf')
    l = 0
    for r, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == req:
            if r - l + 1 < res_len:
                res_l, res_len = l, r - l + 1
            lc = s[l]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                have -= 1
            l += 1
    return "" if res_len == float('inf') else s[res_l:res_l + res_len]
```

### TypeScript
```typescript
export function minWindow(s: string, t: string): string {
  if (!t) return '';
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const win = new Map<string, number>();
  let have = 0, req = need.size, l = 0, resL = 0, resLen = Infinity;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    win.set(c, (win.get(c) ?? 0) + 1);
    if (need.has(c) && win.get(c) === need.get(c)) have++;
    while (have === req) {
      if (r - l + 1 < resLen) { resLen = r - l + 1; resL = l; }
      const lc = s[l++];
      win.set(lc, win.get(lc)! - 1);
      if (need.has(lc) && win.get(lc)! < need.get(lc)!) have--;
    }
  }
  return resLen === Infinity ? '' : s.slice(resL, resL + resLen);
}
```

### C++
```cpp
string minWindow(string s, string t) {
    int need[128] = {0}; int rem = t.size(), l = 0, bestL = 0, bestLen = INT_MAX;
    for (char c : t) need[(unsigned char)c]++;
    for (int r = 0; r < (int)s.size(); ++r) {
        if (need[(unsigned char)s[r]]-- > 0) rem--;
        while (rem == 0) {
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
            if (++need[(unsigned char)s[l++]] > 0) rem++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}
```

### Java
```java
String minWindow(String s, String t) {
    int[] need = new int[128]; for (char c : t.toCharArray()) need[c]++;
    int rem = t.length(), l = 0, bestL = 0, bestLen = Integer.MAX_VALUE;
    for (int r = 0; r < s.length(); r++) {
        if (need[s.charAt(r)]-- > 0) rem--;
        while (rem == 0) {
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
            if (++need[s.charAt(l++)] > 0) rem++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}
```

### Go
```go
func minWindow(s, t string) string {
    var need [128]int
    for i := range t { need[t[i]]++ }
    rem, l, bestL, bestLen := len(t), 0, 0, math.MaxInt
    for r := range s {
        if need[s[r]] > 0 { rem-- }
        need[s[r]]--
        for rem == 0 {
            if r-l+1 < bestLen { bestLen = r - l + 1; bestL = l }
            need[s[l]]++
            if need[s[l]] > 0 { rem++ }
            l++
        }
    }
    if bestLen == math.MaxInt { return "" }
    return s[bestL : bestL+bestLen]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Comparing `have == need` counts UNIQUE required characters meeting their quota, NOT total characters in `t`.

### Follow-ups
- Filtered sliding window only visits indices of `s` that exist in `t` (huge speedup when `s` is mostly irrelevant text).