剑指 Offer II 017. 含有所有字符的最短字符串

class Solution {
    public String minWindow(String s, String t) {
        // 返回含有t最短子字符串
        if (s == null || t == null) return "";
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        int left = 0, right = 0, valid = 0, minLen = Integer.MAX_VALUE, start = 0, len = s.length();
        Map<Character, Integer> windows = new HashMap<>();
        Map<Character, Integer> need    = new HashMap<>();
        // init
        for (char c : tChars) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        // slide windows
        while (right < len) {
            char add = sChars[right];
            right++;
            if (need.containsKey(add)) {
                // first：increase character count
                windows.put(add, windows.getOrDefault(add, 0) + 1);
                if (windows.get(add).equals(need.get(add))) {
                    valid++;
                }
            }
            // shrink left 
            while (valid >= need.size()) {
                if (valid == need.size()) {
                    if (right - left < minLen) {
                        minLen = right - left;
                        start = left;
                    }
                }
                char remove = sChars[left];
                if (need.containsKey(remove)) {
                    int beforeCount = windows.get(remove);
                    if (need.get(remove).equals(beforeCount)) {
                        valid--;
                    }
                    windows.put(remove, beforeCount - 1);
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}