LeetCode 76. Minimum Window Substring

[Woodyiiiiiii]

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.

---

这道题是典型的滑动窗口问题——右指针滑动，直至窗口内包含所有的匹配串字符，更新窗口大小和结果子串，然后左移左指针，直至窗口不包含所有的匹配串字符，再继续移动右指针。如此遍历数组，直至右指针到原字符串边界，时间复杂度为O(n)。
一开始我使用的是HashSet来判断是否匹配，然而没有考虑匹配串有重复字符的情况。我看了大佬的博客后，明白最好使用HashMap(也可以使用双数组)，保存匹配串字符和出现情况，并且用一个变量cnt记录是否达到匹配串的字符长度。
代码思路是首先遍历匹配串， 存入HaspMap中，然后遍历原串，如果包含，则相应的HashMap的Key的Value值减少，并同时判断引用数是否足够或者溢出。到窗口包含所有匹配串字符，再比对更新结果。左指针移动注意要对cnt和HashMap更新。

class Solution {
    public String minWindow(String s, String t) {
        String res = new String();
        HashMap<Character, Integer> letterCnt = new HashMap();
        int left = 0, cnt = 0, minLen = Integer.MAX_VALUE;
        for (int i = 0; i < t.length(); ++i) {
            char c = t.charAt(i);
            //++letterCnt[c];
            if (!letterCnt.containsKey(c)) {
                letterCnt.put(c, 1);
            }
            else {
                int k = letterCnt.get(c);
                letterCnt.replace(c, k + 1);
            }
        }
        for (int i = 0; i < s.length(); ++i) {
            //if (--letterCnt[s[i]] >= 0) ++cnt;
            if (letterCnt.containsKey(s.charAt(i))) {
                int k = letterCnt.get(s.charAt(i));
                letterCnt.replace(s.charAt(i), k - 1);
                if (letterCnt.get(s.charAt(i))>= 0)
                    ++cnt;
            } 
            while (cnt == t.length()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    // System.out.println(left + " " + i + 1);
                    res = s.substring(left, i + 1);
                }
                //if (++letterCnt[s[left]] > 0) --cnt;
                if (letterCnt.containsKey(s.charAt(left))) {
                    int k = letterCnt.get(s.charAt(left));
                    letterCnt.replace(s.charAt(left), k + 1);
                    if (letterCnt.get(s.charAt(left)) > 0)
                        --cnt;
                }
                ++left;
            }
        }
        return res;
    }
}

cpp的写法方便多了，有下标可以直接更新HaspMap。

class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        unordered_map<char, int> letterCnt;
        int left = 0, cnt = 0, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return res;
    }
};

---

参考资料:

• LeetCode原题
• [LeetCode] 76. Minimum Window Substring grandyang/leetcode#76

相似题目:

• 3. Longest Substring Without Repeating Characters