Minimum Window Substring

Given strings s and t, return the minimum window in s that contains all characters of t. If no such window exists, return empty string.

Example 1

Input: s="ADOBECODEBANC", t="ABC" → Output: "BANC"

Example 2

Input: s="a", t="a" → Output: "a"

Solution Approach

Sliding window with character frequency maps. Expand right until window contains all t chars, then shrink from left to minimize window while still valid.

Build frequency map for t (need[]).
Expand right: add s[right] to window map, if it satisfies a needed char increment formed count.
When formed == required (all chars satisfied): try shrinking left, update min window.
Shrink: remove s[left] from window map; if needed char drops below required, decrement formed.

Java

import java.util.*;

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128], have = new int[128];
        int required = 0;
        for (char c : t.toCharArray()) { need[c]++; if (need[c] == 1) required++; }
        int formed = 0, left = 0, minLen = Integer.MAX_VALUE, start = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            have[c]++;
            if (need[c] > 0 && have[c] == need[c]) formed++;
            while (formed == required) {
                if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; }
                have[s.charAt(left)]--;
                if (need[s.charAt(left)] > 0 && have[s.charAt(left)] < need[s.charAt(left)]) formed--;
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

Time Complexity: O(|S| + |T|)
Space Complexity: O(|S| + |T|)