73. Minimum Window Substring

Grow the window on the right until it "has" t; then greedily shrink from the left to minimize. A counter have that equals len(t_needs) tells us the window is valid.

Approach

1. need = Counter(t); required = len(need).
2. Expand r. For each new char, if it matches a needed count, increment have.
3. While have == required, record the current window if it's smaller, then shrink l. If removing the left char drops a needed count below the target, decrement have.

import java.util.*;

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        int required = need.size();
        Map<Character, Integer> window = new HashMap<>();
        int have = 0, bestLen = Integer.MAX_VALUE, bestL = 0, bestR = 0;
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            char ch = s.charAt(r);
            window.merge(ch, 1, Integer::sum);
            if (need.containsKey(ch) && window.get(ch).intValue() == need.get(ch).intValue()) {
                have++;
            }
            while (have == required) {
                if (r - l + 1 < bestLen) {
                    bestLen = r - l + 1;
                    bestL = l;
                    bestR = r;
                }
                char left = s.charAt(l);
                window.merge(left, -1, Integer::sum);
                if (need.containsKey(left) && window.get(left) < need.get(left)) {
                    have--;
                }
                l++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestR + 1);
    }
}