Problem description:

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.

Solution:

  1. create counter for target string, know how many for each char
  2. walk through array with start, end pointers
  3. use independent variable target_len to know if we have all char in t
  4. when find s[end] is needed, subtract target_len
  5. when target_len is 0, means current window contains every letter in t, check if it’s smaller than existed res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	def minWindow(self, s:str, t:str) -> str:
			target = Counter(t)
        start, end = 0, 0
        res = ""
        target_len = len(t)
        
        for end in range(len(s)):
            if target[s[end]] > 0:
                target_len -= 1
            
            target[s[end]] -= 1
            while target_len == 0:
                if not res or len(res) > len(s[start:end+1]):
                    res = s[start:end+1]
                
                target[s[start]] += 1
                if target[s[start]] > 0:
                    target_len += 1
                start += 1
        return res

Solution C++

Since we need to solve this problem in $O(n)$, so we can not use brute force or sorting. We can use a hash table with characters that appeared in T as key, and number of appearance as value.

  • walk through T, store in map
  • walk through S. If meet a character c appeared in T, map[c]–. Keep going until we have a window that contains every character in T.
  • Move the left boundary of the window, skip characters that do not exist in T. Skip a character if it appears in S more that appears in T.
    example:
    S: aaaabb
    T: ab
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string minWindow(string S, string T) {
        if (T.size() > S.size()) return "";
        string res = "";
        int left = 0, count = 0, minLen = S.size() + 1;
        unordered_map<char, int> m;
        for (int i = 0; i < T.size(); ++i) {
            if (m.find(T[i]) != m.end()) ++m[T[i]];
            else m[T[i]] = 1;
        }
        for (int right = 0; right < S.size(); ++right) {
            if (m.find(S[right]) != m.end()) { //found a character appeared in both S and T
                --m[S[right]];
                if (m[S[right]] >= 0) ++count;
                while (count == T.size()) { //find a valid window that contains every characters in T
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        res = S.substr(left, minLen);
                    }
                    if (m.find(S[left]) != m.end()) {
                        ++m[S[left]]; //s[left] is a char in T
                        if (m[S[left]] > 0) --count;
                    }
                    ++left;
                }
            }
        }
        return res;
    }
};

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> map(128,0);
        for(auto c: t) map[c]++;
        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
        while(end<s.size()){
            if(map[s[end++]]-->0) counter--; //in t
            while(counter==0){ //valid
                if(end-begin<d)  d=end-(head=begin);
                if(map[s[begin++]]++==0) counter++;  //make it invalid
            }  
        }
        return d==INT_MAX? "":s.substr(head, d);
    }
};

Solution 3:

It’s the same template as https://goo.gl/AJ5Sw7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> map;
        for(auto c: t)
            map[c]++;
        
        string res;
        int start= 0, end= 0, count= map.size(), len= INT_MAX, head= 0;
        
        while(end< s.length()){
            if(map.find(s[end]) != map.end() ){
                //can find this char in the dictionary, two strings both have this char
                map[s[end]]--;
                if(map[s[end]] == 0)
                    count--;
            }
            end++;
            
            while(count == 0){
                if(map.find(s[start]) != map.end()){
                    map[s[start]]++;
                    if(map[s[start]] > 0)
                        count++;
                }
                if(len> end-start){
                    len= end- start;
                    head= start;
                }
                start++;
            }
        }
        
        return len == INT_MAX? res: s.substr(head, len);
    }
};

time complexity: $O(n)$
reference:
https://goo.gl/1JwyJD
https://goo.gl/pAMsMh
https://goo.gl/B6FoMj
https://goo.gl/cHbo8L