题解 | 牛群名字覆盖

1. 最小覆盖子串问题。
2. hash 的写法是精髓。

import java.util.*;


class Solution {
    private boolean check(int[] hash) {
        for (int i : hash) {
            if (i < 0) {
                return false;
            }
        }
        return true;
    }

    public String minWindow(String s, String t) {
        int[] hash = new int[128];
        for (int i = 0; i < t.length(); ++i) {
            --hash[t.charAt(i)];
        }

        final int n = s.length();
        final char[] cs = s.toCharArray();
        int l = 0;
        int min_l = -1, min_r = -1;
        for (int r = 0; r < n; ++r) {
            ++hash[s.charAt(r)];
            if (check(hash)) {
                while (l <= r && check(hash)) {
                    --hash[s.charAt(l)];
                    ++l;
                }
                if (min_r == -1 || min_r - min_l + 1 > r - l + 2) {
                    min_l = l - 1;
                    min_r = r;
                }
            }
        }
        if (min_r == -1) {
            return "";
        }
        return s.substring(min_l, min_r + 1);
    }
}