Minimum Window Substring

Approach Summary

Expand the window to include all required characters, then shrink from the left while the window remains valid. Track counts with two frequency maps.

Full Solution & Approach

This is the hardest sliding window variant because the window must contain every character of t, with the correct counts. Maintain two frequency maps: need (target counts from t) and have (counts inside the current window). Expand right until the window contains all of t — tracked with a matched counter that increments when a character reaches its required count and decrements when it falls below. Once matched === t.length, the window is valid, so record it and shrink from the left, each time removing a character and re-checking matched. Keep shrinking until the window becomes invalid, then expand right again. The running best (start index and length) is updated whenever a valid window is found. Because both pointers only move forward and each window operation is O(1) against the maps, the whole scan is O(n + m).

Right pointer advances n times and left pointer at most n times, each with O(1) map operations — O(n) time, plus O(m) to build the target counts. Two maps of at most the alphabet size give O(min(alphabet, n)) space.

Solution Code

Solution

def min_window(s: str, t: str) -> str:
    from collections import Counter
    if not t:
        return ""
    need = Counter(t)
    have = {}
    matched = 0
    left = 0
    best = (0, float('inf'))
    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            matched += 1
        while matched == len(need):
            if right - left + 1 < best[1] - best[0] + 1:
                best = (left, right)
            left_ch = s[left]
            if left_ch in need and have[left_ch] == need[left_ch]:
                matched -= 1
            have[left_ch] -= 1
            left += 1
    return "" if best[1] == float('inf') else s[best[0]:best[1] + 1]

function minWindow(s, t) {
  if (!t) return "";
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  const have = new Map();
  let matched = 0;
  let left = 0;
  let bestStart = 0;
  let bestLen = Infinity;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    have.set(ch, (have.get(ch) || 0) + 1);
    if (need.has(ch) && have.get(ch) === need.get(ch)) matched++;
    while (matched === need.size) {
      const len = right - left + 1;
      if (len < bestLen) { bestLen = len; bestStart = left; }
      const leftCh = s[left];
      if (need.has(leftCh) && have.get(leftCh) === need.get(leftCh)) matched--;
      have.set(leftCh, have.get(leftCh) - 1);
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}

public String minWindow(String s, String t) {
    if (t.isEmpty()) return "";
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    Map<Character, Integer> have = new HashMap<>();
    int matched = 0, left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        have.merge(ch, 1, Integer::sum);
        if (need.containsKey(ch) && have.get(ch).equals(need.get(ch))) matched++;
        while (matched == need.size()) {
            int len = right - left + 1;
            if (len < bestLen) { bestLen = len; bestStart = left; }
            char leftCh = s.charAt(left);
            if (need.containsKey(leftCh) && have.get(leftCh).equals(need.get(leftCh))) matched--;
            have.merge(leftCh, -1, Integer::sum);
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

string minWindow(const string& s, const string& t) {
    if (t.empty()) return "";
    unordered_map<char,int> need, have;
    for (char c : t) need[c]++;
    int matched = 0, left = 0, bestStart = 0, bestLen = INT_MAX;
    for (int right = 0; right < (int)s.size(); right++) {
        char ch = s[right];
        have[ch]++;
        if (need.count(ch) && have[ch] == need[ch]) matched++;
        while (matched == (int)need.size()) {
            int len = right - left + 1;
            if (len < bestLen) { bestLen = len; bestStart = left; }
            char lc = s[left];
            if (need.count(lc) && have[lc] == need[lc]) matched--;
            have[lc]--;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}

Edge Cases to Watch

t longer than s — no window can contain it, return ""
t is empty — return "" per problem convention
Characters in t not present in s — impossible, return ""
Window that touches the start or end of s — the pointers naturally cover it

How to Recognize This Pattern

Minimum window containing all of another string

Complexity Analysis

Time Complexity

O(n + m)

Space Complexity

O(m)