Minimum Window Substring

Find minimum window in s containing all characters of t.

Example 1

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

Example 2

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

Solution Approach

Sliding window with frequency maps. Expand right until all chars covered, then shrink left.

Count required frequencies from t
Sliding window: expand right adding chars
When all required chars satisfied: try shrinking left
Update minimum window when valid
Return minimum window substring

Java

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

Time Complexity: O(n+m)
Space Complexity: O(n+m)