76.最小覆盖子串

题目链接：76.最小覆盖子串 (opens new window)

第一眼看这个题目，感觉可以用滑动窗口，处理子串问题比较好用。能不能用要看左边窗口的收缩条件，当s中左边界的字符个数大于t中对应字符个数时，左边界收缩，说明是可以用滑动窗口的。也说到了要统计字符个数，也就是要建立哈希表。不过题目中表示字符串中只有字母，所以哈希表可以简化为字符数组。

//分别为大小写字母分配索引
public int getIndex(char c) {
        return (c >= 'A' && c <= 'Z') ? c - 'A' : c - 'a' + 26;
}
public String minWindow(String s, String t) {
    int[] hash_s = new int[52];
    int[] hash_t = new int[52];
}

当什么时候获得满足条件的字符串呢，也就是t中的字符个数全部小于s对应字符个数，于是我们设立一个valid变量表示有效字符个数，当一个字符满足上述条件时就把valid减一。先获得valid初始值：

int valid = 0;
for (char c : t.toCharArray()) {
    if (hash_t[getIndex(c)] == 0)
        valid++;
    hash_t[getIndex(c)]++;
}

然后就是滑动窗口运行过程了，具体过程写在注释中了。

for (int l = 0, r = 0; r < s.length(); r++) {
    hash_s[getIndex(s.charAt(r))]++;
    //字符s.charAt(r)在s中已经满足个数条件
    if (hash_t[getIndex(s.charAt(r))] == hash_s[getIndex(s.charAt(r))])
        valid--; 
    //左边字符有多余，收缩窗口
    while (l < r) {
        if (hash_s[getIndex(s.charAt(l))] > hash_t[getIndex(s.charAt(l))]){                   
            hash_s[getIndex(s.charAt(l))]--;
            l++;
        }
        else break;                   
    }
    // t中所有字符都已满足个数条件，这里是判最短
    if (valid == 0 && (res.isEmpty() || res.length() > r - l + 1))
        res = s.substring(l, r + 1);
}
return res;