Blind 75Hard

Minimum Window Substring — Sliding Window with Counts

Expand the window to satisfy the requirement, then shrink from the left to find the smallest valid window.

Sliding WindowHash Map

View problem on LeetCode

Problem Statement

Given strings s and t, return the minimum window in s that contains all characters of t.

Why This Problem Matters

Quintessential sliding window problem combining expansion and contraction.
Requires precise bookkeeping of frequencies and satisfied counts.
Frequently asked to test mastery of window invariants.

Thought Process

Count required characters

Build a frequency map for t and track how many unique characters still need satisfying.

Expand right pointer until requirement met

Decrease required count when a character’s frequency hits zero.

Contract left pointer greedily

While the window remains valid, shrink from the left and update the best window length.

Step-by-Step Reasoning

Populate need map with counts from t and set required = need.size().
Move right pointer across s, decrementing counts and reducing required when a count hits zero.
When required becomes zero, try shrinking from the left while maintaining validity.
Track the smallest window indices and return the substring if found.

Dry Run

s = "ADOBECODEBANC", t = "ABC"

Window expands to "ADOBEC" then shrinks to "BANC" as the minimum.

s shorter than t

Algorithm never finds required == 0; returns empty string.

Complexity Analysis

Time

O(|s| + |t|)

Space

O(|Σ|)

Why

Each pointer advances at most |s| steps; maps store counts for alphabet Σ.

Annotated Solution

JAVA

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
  public String minWindow(String s, String t) {
    if (t.length() == 0 || s.length() < t.length()) {
      return "";
    }

    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
      need.merge(c, 1, Integer::sum);
    }

    int required = need.size();
    int formed = 0;
    Map<Character, Integer> window = new HashMap<>();
    int left = 0;
    int bestLen = Integer.MAX_VALUE;
    int bestLeft = 0;

    for (int right = 0; right < s.length(); right += 1) {
      char c = s.charAt(right);
      window.merge(c, 1, Integer::sum);
      if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
        formed += 1;
      }

      while (formed == required) {
        if (right - left + 1 < bestLen) {
          bestLen = right - left + 1;
          bestLeft = left;
        }
        char leftChar = s.charAt(left);
        window.put(leftChar, window.get(leftChar) - 1);
        if (need.containsKey(leftChar) && window.get(leftChar) < need.get(leftChar)) {
          formed -= 1;
        }
        left += 1;
      }
    }

    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestLeft, bestLeft + bestLen);
  }
}

Two-pointers expand and contract the window while hash maps track character counts; formed counts how many requirements are satisfied.

Common Pitfalls

Forgetting to increment the left character back in the map causes windows to appear valid when they are not.
Not using a HashMap or array keyed by characters leads to O(n^2) lookups.
Missing the case where no window exists should return an empty string.

Follow-Up Questions

How would you adapt this for case-insensitive matching or Unicode?
Can you solve the minimum window substring with distinct characters only?

Key Takeaways

Sliding windows require careful tracking of when constraints become satisfied.

Maintain auxiliary structures that represent the window state succinctly.

This template generalises to many substring covering problems.