76. Minimum Window Substring

Leetcode Hash Table Two Pointers String

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity $O(n)$.

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in $S$ that covers all characters in $T$, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in $S$.

分析

滑动窗口题，该题型出现在字符串中，往往涉及两个字符串。既然是滑动窗口，那必然需要左指针和右指针维持滑动窗口的位置。不断移动左指针和右指针，直到右指针移动到字符串末尾。可以用一个哈希表map存储需要匹配的每个不同字符的个数，用required表示需要匹配的不同字符个数。当右指针指向的字符匹配时，将map中相应的匹配的字符个数减去1；当该字符的需要匹配数等于0时，也就是该字符已完成匹配，把required减去1。当required等于1时，也就是所有字符都匹配完成时，这个滑动窗口就是匹配的窗口，这时试图移动左指针向前，直到该滑动窗口不再匹配。重复上述过程，可以寻找到最小的窗口。

public String minWindow(String s, String t) {

    if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";

    // 哈希表保存所有的t中不同字符的个数
    Map<Character, Integer> map = new HashMap<>();
    for (char c : t.toCharArray())
        map.put(c, map.getOrDefault(c, 0) + 1);

    // t中不同字符的个数，即滑动窗口中需要匹配的不同字符个数
    // 当required = 0， 即完成匹配
    int required = map.size();

    // 左右指针
    int l = 0, r = 0;

    // 窗口长度，窗口的左边
    int minLength = Integer.MAX_VALUE, minLeft = 0;

    while (r < s.length()) {
        // 把当前字符加入到窗口中
        char c = s.charAt(r);
        if (map.containsKey(c)) map.put(c, map.getOrDefault(c, 0) - 1);

        // 如果当前字符在滑动窗口中的出现的个数等于需要的个数，那么把需要匹配的字符数required减去1
        if (map.containsKey(c) && map.get(c) == 0) required--;

        // 尝试收缩滑动窗口，直到最佳
        while (required == 0) {
            c = s.charAt(l);
            // 保存当前窗口
            if (r - l + 1 < minLength) {
                minLength = r - l + 1;
                minLeft = l;
            }

            // 由于窗口缩小了，需要最左边字符的数量加1
            if (map.containsKey(c))  map.put(c, map.get(c) + 1);
            // 字符数量不等于0，表明需要匹配的字符数required加1，滑动窗口不再符合
            if (map.containsKey(c) && map.get(c) > 0) required++;
            // 移动左指针向前，寻找一个新的窗口
            l++;
        }

        // 当收缩窗口完成以后，继续扩展窗口
        r++;
    }

    return minLength == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLength);
}

值得注意的是其实if (map.containsKey(c))这个判断可以去掉，因为如果$t$中不出现的字符加入的话，由于起始值为0，所以其在哈希表中的值始终为负，不影响判断。

有没有更快的方法？其实所有用哈希表存储字符的题目都可以用整型数组int[] array代替HashMap:

public String minWindow(String s, String t) {

    if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";

    // 哈希表保存所有的t中所有的字符的计数
    int [] map = new int[128];
    for (char c : t.toCharArray())
        map[c]++;

    // t中字符的数量，窗口中需要匹配的字符数
    int required = 0;
    for (int i : map)
        if (i > 0) required++;

    // 左右指针
    int l = 0, r = 0;

    // 窗口长度，窗口的左边
    int minLength = Integer.MAX_VALUE, minLeft = 0;

    while (r < s.length()) {
        // 把当前字符加入到窗口中
        char c = s.charAt(r);
        map[c]--;

        // 如果当前字符在滑动窗口中的出现的个数等于需要的个数，那么把需要匹配的字符数required减去1
        if (map[c] == 0) required--;

        // 尝试收缩滑动窗口，直到最佳
        while (required == 0) {
            c = s.charAt(l);
            // 保存当前窗口
            if (r - l + 1 < minLength) {
                minLength = r - l + 1;
                minLeft = l;
            }

            // 由于窗口缩小了，需要最左边字符的数量加1
            map[c]++;
            // 字符数量不等于0，表明需要匹配的字符数required加1，滑动窗口不再符合
            if (map[c] > 0) required++;
            // 移动左指针向前，寻找一个新的窗口
            l++;
        }

        // 当收缩窗口完成以后，继续扩展窗口
        r++;
    }

    return minLength == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLength);
}