【D39】最小覆盖子串 (LC 76)

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

• 滑动窗口
  附上讨论区一篇讲得很好理解的题解：简简单单，非常容易理解的滑动窗口思想

class Solution {
    public String minWindow(String s, String t) {
        //需求的字符个数
        int count = t.length();
        //need数组记录窗口中的字符，以及每个字符被需要的数量
        //英文字母的ASCII码值范围a-z：97-122；A-Z：65-90
        int[] need = new int[123];
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        
        //size记录窗口大小，start是最小覆盖串开始的index
        int size = Integer.MAX_VALUE, start = 0;

        //窗口左右边界
        int l = 0, r = 0;
        while (r < s.length()) {
            char c = s.charAt(r);
            //需要字符c
            if (need[c] > 0) {
                count--;
            }
            //把右边的字符加入窗口
            need[c]--;

            //如果窗口中已经包含所有字符
            if (count == 0) { 
                while (l < r && need[s.charAt(l)] < 0) {
                    //左指针右移，并释放移动出窗口的字符（不被需要的字符）
                    need[s.charAt(l)]++;
                    l++;
                }
                //遇到需要的字符时左指针停止右移，更新最小窗口
                if (r - l + 1 < size) {
                    size = r - l + 1;
                    start = l;
                }
                //l向右移动后窗口肯定不能满足了 重新开始循环
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}