76. Minimum Window Substring (Hard)

Problem

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return the empty string. A solution is guaranteed to be unique.

Example

s = "ADOBECODEBANC", t = "ABC" → "BANC"
s = "a", t = "a" → "a"
s = "a", t = "aa" → ""

LeetCode 76 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, every substring

Check every substring of s and compare its character counts to those of t.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = Counter(t)                                         # L1: O(|t|)
    n = len(s)
    best = ""
    for i in range(n):                                        # L2: outer loop, n iterations
        for j in range(i + len(t), n + 1):                   # L3: inner loop, O(n) per outer
            window = Counter(s[i:j])                          # L4: slice + Counter, O(n) each
            if all(window[ch] >= need[ch] for ch in need):   # L5: O(k) check
                if not best or j - i < len(best):
                    best = s[i:j]                             # L6: O(n) slice
    return best

function minWindow(s: string, t: string): string {
    if (!s || !t) return '';
    const need = new Map<string, number>();
    for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
    const n = s.length;
    let best = '';
    for (let i = 0; i < n; i++) {                                    // L2: outer loop
        for (let j = i + t.length; j <= n; j++) {                   // L3: inner loop
            const window = new Map<string, number>();
            for (const ch of s.slice(i, j))                         // L4: Counter, O(n) each
                window.set(ch, (window.get(ch) ?? 0) + 1);
            let valid = true;
            for (const [ch, cnt] of need)                           // L5: O(k) check
                if ((window.get(ch) ?? 0) < cnt) { valid = false; break; }
            if (valid && (!best || j - i < best.length))
                best = s.slice(i, j);                               // L6: O(n) slice
        }
    }
    return best;
}

func minWindow(s string, t string) string {
  if s == "" || t == "" {
    return ""
  }
  need := make(map[byte]int)
  for i := 0; i < len(t); i++ {
    need[t[i]]++
  }
  n := len(s)
  best := ""
  for i := 0; i < n; i++ {                              // L2: outer loop
    window := make(map[byte]int)
    for j := i + len(t); j <= n; j++ {               // L3: inner loop
      window[s[j-1]]++                              // L4: build window incrementally
      valid := true
      for ch, cnt := range need {                   // L5: O(k) check
        if window[ch] < cnt {
          valid = false
          break
        }
      }
      if valid && (best == "" || j-i < len(best)) {
        best = s[i:j]                             // L6: O(n) slice
      }
    }
  }
  return best
}

final class Solution {
    func minWindow(_ s: String, _ t: String) -> String {
        let text = Array(s)
        let required = frequencies(Array(t))
        var bestStart = 0, bestLength = Int.max
        for start in text.indices {
            var counts: [Character: Int] = [:]
            for end in start..<text.count {
                counts[text[end], default: 0] += 1
                if covers(counts, required), end - start + 1 < bestLength {
                    bestStart = start
                    bestLength = end - start + 1
                    break
                }
            }
        }
        return bestLength == Int.max ? "" : String(text[bestStart..<(bestStart + bestLength)])
    }

    private func frequencies(_ values: [Character]) -> [Character: Int] {
        values.reduce(into: [:]) { $0[$1, default: 0] += 1 }
    }

    private func covers(_ counts: [Character: Int], _ required: [Character: Int]) -> Bool {
        required.allSatisfy { counts[$0.key, default: 0] >= $0.value }
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in t.

Line	Per-call cost	Times executed	Contribution
L1 (Counter(t))	$O(\\|t\\|)$	1	$O(\\|t\\|)$
L2 (outer loop)	$O(1)$	n	$O(n)$
L3 (inner loop)	$O(1)$	$O(n²)$ total	$O(n²)$
L4 (Counter build)	$O(n)$	$O(n²)$	$O(n³)$ ← dominates
L5 (all check)	$O(k)$	$O(n²)$	$O(n² · k)$

L4 is the killer: building a Counter from a slice requires scanning the slice, which is $O(n)$ per call, and we call it $O(n²)$ times.

Complexity

Time: $O(n³)$ or worse, driven by L4 (Counter on every substring pair).
Space: $O(k)$ .

Approach 2: Expand-then-contract sliding window, full counter compare each step

Expand right; when the window contains all of t, contract left to shrink.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = Counter(t)                                          # L1: O(|t|)
    window = Counter()                                         # L2: O(1)
    left = 0
    best = ""
    for right, ch in enumerate(s):                            # L3: outer loop, n iterations
        window[ch] += 1                                        # L4: O(1)
        while all(window[c] >= need[c] for c in need):        # L5: O(k) per check
            if not best or right - left + 1 < len(best):
                best = s[left:right + 1]                      # L6: O(n) slice
            window[s[left]] -= 1                              # L7: O(1)
            left += 1                                         # L8: O(1)
    return best

function minWindow(s: string, t: string): string {
    if (!s || !t) return '';
    const need = new Map<string, number>();
    for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
    const window = new Map<string, number>();                          // L2: O(1)
    let left = 0;
    let best = '';
    for (let right = 0; right < s.length; right++) {                 // L3: outer loop
        const ch = s[right];
        window.set(ch, (window.get(ch) ?? 0) + 1);                   // L4: O(1)
        const valid = () => {                                         // L5: O(k) per check
            for (const [c, cnt] of need)
                if ((window.get(c) ?? 0) < cnt) return false;
            return true;
        };
        while (valid()) {
            if (!best || right - left + 1 < best.length)
                best = s.slice(left, right + 1);                      // L6: O(n) slice
            window.set(s[left], window.get(s[left])! - 1);           // L7: O(1)
            left++;                                                   // L8: O(1)
        }
    }
    return best;
}

func minWindow(s string, t string) string {
  if s == "" || t == "" {
    return ""
  }
  need := make(map[byte]int)
  for i := 0; i < len(t); i++ {
    need[t[i]]++
  }
  window := make(map[byte]int)                          // L2: O(1)
  left := 0
  best := ""
  valid := func() bool {                               // L5: O(k) per check
    for ch, cnt := range need {
      if window[ch] < cnt {
        return false
      }
    }
    return true
  }
  for right := 0; right < len(s); right++ {            // L3: outer loop
    window[s[right]]++                               // L4: O(1)
    for valid() {
      if best == "" || right-left+1 < len(best) {
        best = s[left : right+1]                 // L6: O(n) slice
      }
      window[s[left]]--                            // L7: O(1)
      left++                                       // L8: O(1)
    }
  }
  return best
}

final class Solution {
    func minWindow(_ s: String, _ t: String) -> String {
        let text = Array(s)
        let required = frequencies(Array(t))
        var window: [Character: Int] = [:]
        var left = 0, bestStart = 0, bestLength = Int.max
        for right in text.indices {
            window[text[right], default: 0] += 1
            while covers(window, required) {
                if right - left + 1 < bestLength { bestStart = left; bestLength = right - left + 1 }
                window[text[left], default: 0] -= 1
                left += 1
            }
        }
        return bestLength == Int.max ? "" : String(text[bestStart..<(bestStart + bestLength)])
    }

    private func frequencies(_ values: [Character]) -> [Character: Int] {
        values.reduce(into: [:]) { $0[$1, default: 0] += 1 }
    }

    private func covers(_ counts: [Character: Int], _ required: [Character: Int]) -> Bool {
        required.allSatisfy { counts[$0.key, default: 0] >= $0.value }
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in t.

Line	Per-call cost	Times executed	Contribution
L1-L2 (init)	$O(\\|t\\|)$	1	$O(\\|t\\|)$
L3 (expand right)	$O(1)$	n	$O(n)$
L4 (increment)	$O(1)$	n	$O(n)$
L5 (all-check)	$O(k)$	$O(n)$ times	$O(n · k)$ ← dominates
L6 (best slice)	$O(n)$	at most n	$O(n²)$ in theory but rarely
L7/L8 (shrink left)	$O(1)$	at most n total	$O(n)$

The all(...) check iterates over all k distinct characters of t every time the window is valid. Since left moves at most n times and right moves n times, L5 fires $O(n)$ times total, giving $O(n · k)$ .

Complexity

Time: $O(n · k)$ , driven by L5 (the $O(k)$ all-check inside the while loop).
Space: $O(k)$ .

Approach 3: Sliding window with “have vs. need” counter (optimal)

Track how many distinct characters of t are fully matched in the current window (have). have == len(need) is a constant-time “valid window” check.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = Counter(t)                                      # L1: O(|t|)
    needed = len(need)                                     # L2: O(1)
    window = Counter()                                     # L3: O(1)
    have = 0                                               # L4: O(1)
    left = 0
    best = (float('inf'), 0, 0)                            # L5: O(1)

    for right, ch in enumerate(s):                         # L6: outer loop, n iterations
        window[ch] += 1                                    # L7: O(1)
        if ch in need and window[ch] == need[ch]:          # L8: O(1) comparison
            have += 1                                      # L9: O(1)
        while have == needed:                              # L10: O(1) guard; shrink loop
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)    # L11: O(1) tuple
            window[s[left]] -= 1                           # L12: O(1)
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1                                  # L13: O(1)
            left += 1                                      # L14: O(1)

    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

function minWindow(s: string, t: string): string {
    if (!s || !t) return '';
    const need = new Map<string, number>();                // L1: O(|t|)
    for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
    const needed = need.size;                             // L2: O(1)
    const window = new Map<string, number>();             // L3: O(1)
    let have = 0;                                         // L4: O(1)
    let left = 0;
    let bestLen = Infinity, bestL = 0, bestR = 0;         // L5: O(1)

    for (let right = 0; right < s.length; right++) {     // L6: outer loop, n iterations
        const ch = s[right];
        window.set(ch, (window.get(ch) ?? 0) + 1);       // L7: O(1)
        if (need.has(ch) && window.get(ch) === need.get(ch)) {  // L8: O(1)
            have++;                                       // L9: O(1)
        }
        while (have === needed) {                         // L10: O(1) guard; shrink loop
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;               // L11: O(1)
                bestL = left; bestR = right;
            }
            const lch = s[left];
            window.set(lch, window.get(lch)! - 1);       // L12: O(1)
            if (need.has(lch) && window.get(lch)! < need.get(lch)!) {
                have--;                                   // L13: O(1)
            }
            left++;                                       // L14: O(1)
        }
    }
    return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}

func minWindow(s string, t string) string {
  if s == "" || t == "" {
    return ""
  }
  need := make(map[byte]int)                             // L1: O(|t|)
  for i := 0; i < len(t); i++ {
    need[t[i]]++
  }
  needed := len(need)                                    // L2: O(1)
  window := make(map[byte]int)                           // L3: O(1)
  have := 0                                              // L4: O(1)
  left := 0
  bestLen := 1<<63 - 1                                   // L5: O(1)
  bestL, bestR := 0, 0

  for right := 0; right < len(s); right++ {             // L6: outer loop, n iterations
    ch := s[right]
    window[ch]++                                       // L7: O(1)
    if cnt, ok := need[ch]; ok && window[ch] == cnt { // L8: O(1)
      have++                                         // L9: O(1)
    }
    for have == needed {                               // L10: O(1) guard; shrink loop
      if right-left+1 < bestLen {
        bestLen = right - left + 1                 // L11: O(1)
        bestL = left
        bestR = right
      }
      lch := s[left]
      window[lch]--                                  // L12: O(1)
      if cnt, ok := need[lch]; ok && window[lch] < cnt {
        have--                                     // L13: O(1)
      }
      left++                                         // L14: O(1)
    }
  }
  if bestLen == 1<<63-1 {
    return ""
  }
  return s[bestL : bestR+1]
}

final class Solution {
    func minWindow(_ s: String, _ t: String) -> String {
        let text = Array(s)
        let required = Array(t).reduce(into: [Character: Int]()) { $0[$1, default: 0] += 1 }
        var window: [Character: Int] = [:]
        var have = 0, left = 0, bestStart = 0, bestLength = Int.max
        for right in text.indices {
            let character = text[right]
            window[character, default: 0] += 1
            if window[character] == required[character] { have += 1 }
            while have == required.count {
                if right - left + 1 < bestLength { bestStart = left; bestLength = right - left + 1 }
                let removed = text[left]
                window[removed, default: 0] -= 1
                if let needed = required[removed], window[removed, default: 0] < needed { have -= 1 }
                left += 1
            }
        }
        return bestLength == Int.max ? "" : String(text[bestStart..<(bestStart + bestLength)])
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in t.

Line	Per-call cost	Times executed	Contribution
L1-L5 (init)	$O(\\|t\\|)$	1	$O(\\|t\\|)$
L6 (expand right)	$O(1)$ body	n	$O(n)$ ← dominates
L7/L8/L9 (window update)	$O(1)$	n	$O(n)$
L10-L14 (shrink left)	$O(1)$ per step	at most n total	$O(n)$

The key upgrade over Approach 2: have is an integer that tracks how many distinct characters of t are fully satisfied. Checking have == needed is $O(1)$ rather than $O(k)$ . Each character crosses the window boundary at most twice (once entering, once leaving), so the total work is $O(n)$ .

Complexity

Time: $O(n)$ , driven by L6/L7/L8 (the single linear pass with $O(1)$ window updates).
Space: $O(k)$ .

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Brute force	$O(n³)$	$O(k)$
Window + $O(k)$ check	$O(n · k)$	$O(k)$
Window + have/need counter	$O(n)$	$O(k)$

The “have vs. need” pattern is the workhorse of hard sliding-window problems. The same template solves “substring with at most k distinct,” “smallest subarray containing X”, etc.

Test cases

# Quick smoke tests - paste into a REPL or save as test_076.py and run.
# Uses the optimal Approach 3 implementation.

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
    need = Counter(t)
    needed = len(need)
    window = Counter()
    have = 0
    left = 0
    best = (float('inf'), 0, 0)

    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            have += 1
        while have == needed:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1

    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

def _run_tests():
    assert min_window("ADOBECODEBANC", "ABC") == "BANC"
    assert min_window("a", "a") == "a"
    assert min_window("a", "aa") == ""           # t requires two a's, s has one
    assert min_window("", "a") == ""             # empty s
    assert min_window("abc", "") == ""           # empty t
    assert min_window("aa", "aa") == "aa"        # exact match with duplicates
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function minWindow(s: string, t: string): string {
    if (!s || !t) return '';
    const need = new Map<string, number>();
    for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
    const needed = need.size;
    const window = new Map<string, number>();
    let have = 0, left = 0;
    let bestLen = Infinity, bestL = 0, bestR = 0;
    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        window.set(ch, (window.get(ch) ?? 0) + 1);
        if (need.has(ch) && window.get(ch) === need.get(ch)) have++;
        while (have === needed) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1; bestL = left; bestR = right;
            }
            const lch = s[left];
            window.set(lch, window.get(lch)! - 1);
            if (need.has(lch) && window.get(lch)! < need.get(lch)!) have--;
            left++;
        }
    }
    return bestLen === Infinity ? '' : s.slice(bestL, bestR + 1);
}

console.assert(minWindow("ADOBECODEBANC", "ABC") === "BANC");
console.assert(minWindow("a", "a") === "a");
console.assert(minWindow("a", "aa") === "");
console.assert(minWindow("", "a") === "");
console.assert(minWindow("abc", "") === "");
console.assert(minWindow("aa", "aa") === "aa");
console.log("all tests pass");

func minWindow(s string, t string) string {
  if s == "" || t == "" {
    return ""
  }
  need := make(map[byte]int)
  for i := 0; i < len(t); i++ {
    need[t[i]]++
  }
  needed := len(need)
  window := make(map[byte]int)
  have, left := 0, 0
  bestLen := 1<<63 - 1
  bestL, bestR := 0, 0
  for right := 0; right < len(s); right++ {
    ch := s[right]
    window[ch]++
    if cnt, ok := need[ch]; ok && window[ch] == cnt {
      have++
    }
    for have == needed {
      if right-left+1 < bestLen {
        bestLen = right - left + 1
        bestL = left
        bestR = right
      }
      lch := s[left]
      window[lch]--
      if cnt, ok := need[lch]; ok && window[lch] < cnt {
        have--
      }
      left++
    }
  }
  if bestLen == 1<<63-1 {
    return ""
  }
  return s[bestL : bestR+1]
}

Strings, input
Hash Tables, need, window, and the have/needed matching trick

Monotonic Queue, deque tactics for maintaining a window minimum or maximum as the window slides.
Sliding Window, contiguous-range tactics for maintaining a valid subarray or substring while endpoints move forward.

76. Minimum Window Substring (Hard)

Problem

Try it yourself

Approach 1: Brute force, every substring

Approach 2: Expand-then-contract sliding window, full counter compare each step

Approach 3: Sliding window with “have vs. need” counter (optimal)

Summary

Test cases

Related data structures

Related concepts