LeetCode 76 - Minimum Window Substring

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).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

[思路]

这道题和Substring with Concatenation of All Words思路非常类似，同样是建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符（也就是这个串不需要包含且仅仅包含字典里面的字符，有一些不在字典的仍然可以满足要求），所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。算法的时间复杂度是O(n),其中n是字符串的长度，因为每个字符再维护窗口的过程中不会被访问多于两次。空间复杂度则是O(字典的大小)，也就是代码中T的长度。

public String minWindow(String S, String T) {
    int m = S.length(), n = T.length();
    Map<Character, Integer> map = new HashMap<>();
    for(int i=0; i<n; i++) {
        char c = T.charAt(i);
        map.put(c, map.containsKey(c) ? map.get(c)+1 : 1);
    }
    int l = 0, r = 0;
    int minStart = 0, minLen = Integer.MAX_VALUE;
    int count = 0;
    for(; r < m; r++) {
        char rc = S.charAt(r); // right char
        if(!map.containsKey(rc)) continue;
        map.put(rc, map.get(rc)-1);
        if(map.get(rc) >= 0) count++;
        
        while(count == n) {
            int len = r-l+1;
            if(len < minLen) {
                minLen = len;
                minStart = l;
            }
            char lc = S.charAt(l); // left char
            if(map.get(lc) != null) {
                map.put(lc, map.get(lc)+1);
                if(map.get(lc)>0) {
                    count--;
                }
            }
            l++;
        }
    }
    if(minLen > m) return "";
    return S.substring(minStart, minStart+minLen);
}

 

我们还可以用两个数组来替代HashMap。

public String minWindow(String s, String t) {
    int[] mapS = new int[256];
    int[] mapT = new int[256];
    for(char c: t.toCharArray()) {
        mapT[c]++;
    }
    int minLen = Integer.MAX_VALUE;
    int left = 0, cnt = 0;
    String res = "";
    for(int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        if(++mapS[c] <= mapT[c]) cnt++;
        if(cnt == t.length()) {
            c = s.charAt(left);
            while(mapS[c] > mapT[c]) {
                mapS[c]--;
                c = s.charAt(++left);
            }
            int len = i-left+1;
            if(len < minLen) {
                minLen = len;
                res = s.substring(left, i+1);
            }
        }
    }
    return res;
}

 

又重构了下以上代码：

string minWindow(string s, string t) {
    vector<int> vs(256), vt(256);
    for(char c:t) {
        vt[c]++;
    }
    int m = s.size(), n = t.size();
    int left = 0, cnt = 0, minLen = INT_MAX;
    string res;
    for(int i=0; i<m; i++) {
        vs[s[i]]++;
        if(!vt[s[i]]) continue;
        if(vs[s[i]] <= vt[s[i]]) {
            cnt++;
        }
        if(cnt == n) {
            while(vs[s[left]] > vt[s[left]]) {
                vs[s[left]]--;
                left++;
            }
            int len = i-left+1;
            if(len < minLen) {
                minLen = len;
                res = s.substr(left, len);
            }
        }
    }
    return res;
}

 

Reference:

https://shepherdyuan.wordpress.com/2014/08/02/minimum-window-substring/