🫥76 minimum window substring

https://leetcode.com/problems/minimum-window-substring/

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> target = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            target.put(t.charAt(i), target.getOrDefault(t.charAt(i), 0) + 1);
        }
        char[] input = s.toCharArray();
        int l = 0;
        int minLen = Integer.MAX_VALUE;
        int ansStart = 0, ansEnd = 0;
        int needed = target.size();
        Map<Character, Integer> window = new HashMap<>();
        for (int r = 0; r < input.length; r++) {
            window.put(input[r], window.getOrDefault(input[r], 0) + 1);
            Integer count = target.get(input[r]);
            if (count != null && count.equals(window.get(input[r]))) {
                needed--;
            }
            while (needed == 0) {
                int curCnt = window.get(input[l]);
                if (curCnt == 1) {
                    window.remove(input[l]);
                } else {
                    window.put(input[l], curCnt - 1);
                }
                if (target.containsKey(input[l])) {
                    if (target.get(input[l]) == curCnt) {
                        needed++;
                    }
                }
                int len = r - l + 1;
                if (needed == 1 && len < minLen) {
                    minLen = len;
                    ansStart = l;
                    ansEnd = r;
                }
                l++;
            }
        }
        if (minLen == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(ansStart, ansEnd + 1);
    }
}

写得有点messy，关键是needed增加和减少的时机是对称的

这道题跟395一样，缩小window都反而会破坏条件，但是这道题为什么可以主动缩小window呢，因为这里求的是min len，由此可以总结出sliding window的两个适用问题：

1. 求max len的时候，需要的是遍历所有满足条件的window，所以j一直扩张到不满足条件再让i移动，滑动窗口只是一种遍历的手段

2. 求min len的时候，需要的是尽可能小的范围内满足条件，所以一旦j满足条件就右移i直至条件不满足

像395那样的题目更加特殊，j扩张只会更加满足条件，这样的情况就得自己创造出条件