Minimum Window Substring

Why it belongs on this sheet

This is the capstone sliding-window problem for many interview tracks. It tests both window validity and shrink logic.

Pattern

Minimum valid window

Approach

Count required characters from t. Expand the right pointer until the window satisfies all requirements, then shrink from the left while it stays valid. Track the shortest valid window seen.

Java solution

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

class Solution {
  public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    for (char ch : t.toCharArray()) {
      need.put(ch, need.getOrDefault(ch, 0) + 1);
    }

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

    for (int right = 0; right < s.length(); right++) {
      char current = s.charAt(right);
      window.put(current, window.getOrDefault(current, 0) + 1);

      if (need.containsKey(current) && window.get(current).intValue() == need.get(current)) {
        formed++;
      }

      while (formed == required) {
        if (right - left + 1 < bestLength) {
          bestLength = right - left + 1;
          bestStart = left;
        }

        char leftChar = s.charAt(left++);
        window.put(leftChar, window.get(leftChar) - 1);

        if (need.containsKey(leftChar) && window.get(leftChar) < need.get(leftChar)) {
          formed--;
        }
      }
    }

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

Complexity

• Time: O(|s| + |t|)
• Space: O(|alphabet|)

Interview note

The clean explanation is "expand to satisfy, shrink to optimize."