MinimumWindowSubstring.java

/**
 * 76. Minimum Window Substring
 * 滑动窗口。用i和j分别指示窗口的两端。
 * 大体思路：
 *
 * 初始化：i和j都为0.
 * while（j还没有到尾部）：
 * * 将j往右移动，直到覆盖所有需要的元素。
 * * 将i往右移动，去除不必要的部分。
 * * 计算此时的窗口长度，与之前的作比较，取最小值。
 * * 将i往右移动一位，使窗口不满足条件，然后重复第一步。
 *
 * 注意因为char是8位，所以可以用128个元素的数组代替哈希。
 * @author LBW
 */
public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c: t.toCharArray()) {
            need[c] += 1;
        }
        int needCount = t.length();
        int res = Integer.MAX_VALUE, start = 0;
        int i = 0, j = 0;
        while (j < s.length()) {
            if (need[s.charAt(j)] > 0) {
                needCount -= 1;
            }
            need[s.charAt(j)] -= 1;
            if (needCount == 0) { // 此时说明滑动窗口里有了该有的元素
                // 尝试将i往右移，得到最小长度
                while (need[s.charAt(i)] < 0) {
                    need[s.charAt(i)] += 1;
                    i += 1;
                }
                if (j - i + 1 < res) {
                    res = j - i + 1;
                    start = i;
                }
                res = Math.min(res, j - i + 1);
                // 将i往右移动一位，循环以上步骤
                need[s.charAt(i++)] += 1;
                needCount += 1;
            }
            j += 1;
        }

        if (res == Integer.MAX_VALUE) {
            return  "";
        }
        else
            return s.substring(start, start + res);
    }
}