06. Minimum Window Substring

Difficulty:HardPattern:Sliding WindowTime:O(|s| + |t|)Space:O(|s| + |t|)

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

How It Works & Algorithmic Design

Solves using Variable Sliding Window with Frequency Counts:

Frequency Map: Build frequency target map for string t. Maintain required = map.size.
Expand Right: Move right pointer over s:
- Decrement character count in map. If count reaches zero, increment formed++.
Contract Left: While formed === required:
- Update min window substring bounds if smaller.
- Shrink left pointer: increment map count. If count becomes $> 0$, decrement formed--.

Why This Approach Works Best

Achieves optimal $O(|s| + |t|)$ linear time complexity and $O(|s| + |t|)$ space without testing all $O(s^2)$ sub-string pairs.

Example Walkthrough

Input: s = "ADOBECODEBANC", t = "ABC"

Find smallest substring containing A, B, C.

Window Shrink: Window "BANC" contains 'A', 'B', 'C' with length 4.

Smallest valid window found.

Output: "BANC"

Minimum window substring.

Answer: Minimum Window Substring implementation

function minWindow(s, t) {
  if (!s || !t) return '';
  const tCount = {};
  for (const ch of t) tCount[ch] = (tCount[ch] || 0) + 1;
  let required = Object.keys(tCount).length;
  let left = 0, right = 0, formed = 0;
  const windowCounts = {};
  let ans = [-1, 0, 0];
  while (right < s.length) {
    const c = s[right];
    windowCounts[c] = (windowCounts[c] || 0) + 1;
    if (tCount[c] && windowCounts[c] === tCount[c]) formed++;
    while (left <= right && formed === required) {
      const cLeft = s[left];
      if (ans[0] === -1 || right - left + 1 < ans[0]) ans = [right - left + 1, left, right];
      windowCounts[cLeft]--;
      if (tCount[cLeft] && windowCounts[cLeft] < tCount[cLeft]) formed--;
      left++;
    }
    right++;
  }
  return ans[0] === -1 ? '' : s.substring(ans[1], ans[2] + 1);
}

💡 Expand right window edge to fulfill target character counts, then contract left edge to find minimal size.

Key Takeaways

Use formed match counter to avoid $O(26)$ frequency comparison inside loops.
Two pointers advance linearly across input string.
Linear time complexity $O(|s| + |t|)$.