Sharing my straightforward O(n) solution with explanation


  • 43
    Z
    string minWindow(string S, string T) {
        string result;
        if(S.empty() || T.empty()){
            return result;
        }
        unordered_map<char, int> map;
        unordered_map<char, int> window;
        for(int i = 0; i < T.length(); i++){
            map[T[i]]++;
        }
        int minLength = INT_MAX;
        int letterCounter = 0;
        for(int slow = 0, fast = 0; fast < S.length(); fast++){
            char c = S[fast];
            if(map.find(c) != map.end()){
                window[c]++;
                if(window[c] <= map[c]){
                    letterCounter++;
                }
            }
            if(letterCounter >= T.length()){
                while(map.find(S[slow]) == map.end() || window[S[slow]] > map[S[slow]]){
                    window[S[slow]]--;
                    slow++;
                }
                if(fast - slow + 1 < minLength){
                    minLength = fast - slow + 1;
                    result = S.substr(slow, minLength);
                }
            }
        }
        return result;
    }
    

    There are three key variables in my solution:

    unordered_map <char, int> map; unordered_map<char, int> window; int letterCounter;
    

    variable "map" is used to indicate what characters and how many characters are in T.

    variable "window" is to indicate what characters and how many characters are between pointer "slow" and pointer "fast".

    Now let's start.

    The first For loop is used to construct variable "map".

    The second For loop is used to find the minimum window.

    The first thing we should do in the second For loop is to find a window which can cover T. I use "letterCounter" to be a monitor. If "letterCounter" is equal to T.length(), then we find this window. Before that, only the first If clause can be executed. However, after we find this window, the second If clause can also be executed.

    In the second If clause, we move "slow" forward in order to shrink the window size. Every time finding a smaller window, I update the result.

    At the end of program, I return result, which is the minimum window.


  • 7
    J

    Thank you. I've rewritten your code (use only one hash map):

    class Solution {
    public:
        string minWindow(string S, string T) {
            if (S.length() < T.length()) return "";
            unordered_map<char, int> counts;
            for (char c : T) {
                auto it = counts.find(c);
                if (it == counts.end()) {
                    counts[c] = 1;
                } else {
                    it->second++;
                }
            }
            int start = 0;
            int length = 0;
            int total = 0;
            for (int head = 0, tail = 0; tail < S.length(); tail++) {
                auto itTail = counts.find(S[tail]);
                if (itTail == counts.end()) continue;
                itTail->second--;
                if (itTail->second >= 0) total++;
                if (total == T.size()) {
                    auto itHead = counts.find(S[head]);
                    while (itHead == counts.end() || itHead->second < 0) {
                        if (itHead != counts.end()) itHead->second++;
                        itHead = counts.find(S[++head]);
                    }
                    if (length == 0 || tail - head + 1 < length) {
                        length = tail - head + 1;
                        start = head;
                    }
                }
            }
            return S.substr(start, length);
        }
    };

  • 8
    D

    Below is my solution in Java:

    import java.util.Queue;
    import java.util.LinkedList;
    public class Solution {
        public String minWindow(String S, String T) {
            HashMap<Character, Integer> mapt = new HashMap<Character, Integer>();
            HashMap<Character, Integer> window = new HashMap<Character, Integer>();
            for(int i = 0; i < T.length(); i++ ){
                char c= T.charAt(i);
                if(!mapt.containsKey(c)){
                    mapt.put(c, 1);
                    window.put(c, 0);
                }else {
                    mapt.put(c, mapt.get(c)+1);
                }
            }
            
            int start = 0;
            int count = 0;
            int minLength = Integer.MAX_VALUE;
            int minStart = 0;
            
            for(int end = 0; end < S.length(); end++){
                char c = S.charAt(end);
                if(mapt.containsKey(c)) {
                    if(window.get(c) < mapt.get(c)){
                        count ++;
                    }
                    window.put(c, window.get(c) + 1);
                }
                if(count >= T.length()){
                    
                    while((!mapt.containsKey(S.charAt(start))) || 
                        window.get(S.charAt(start)) > mapt.get(S.charAt(start))){
                            if(window.containsKey(S.charAt(start)))
                                window.put(S.charAt(start), window.get(S.charAt(start))-1);
                            start++;
                        }
                    if(end-start+1 < minLength){
                        minStart = start;
                        minLength = end-start+1;
                    }
                    
                    count--;
                    window.put(S.charAt(start), window.get(S.charAt(start))-1);
                    start++;
                }
            }
            
            if(minLength == Integer.MAX_VALUE) return "";
            return S.substring(minStart, minStart+minLength);
        }
    }

  • 20
    M

    I think it's better to add these 3 sentences when we are shrinking the window. In your code , letterCounter will never change after it equals to T.length(), but the truth is that if we shrink a certain char, letterCounter will less than T.length, Although your code is accepted, but I think this is a bug.

    Also by adding these sentence, your code will run much faster because of the cut-down of meaningless check.

    string minWindow(string S, string T) {
    string result;
    if(S.empty() || T.empty()){
        return result;
    }
    unordered_map<char, int> map;
    unordered_map<char, int> window;
    for(int i = 0; i < T.length(); i++){
        map[T[i]]++;
    }
    int minLength = INT_MAX;
    int letterCounter = 0;
    for(int slow = 0, fast = 0; fast < S.length(); fast++){
        char c = S[fast];
        if(map.find(c) != map.end()){
            window[c]++;
            if(window[c] <= map[c]){
                letterCounter++;
            }
        }
        if(letterCounter >= T.length()){
            while(map.find(S[slow]) == map.end() || window[S[slow]] > map[S[slow]]){
                window[S[slow]]--;
                slow++;
            }
            if(fast - slow + 1 < minLength){
                minLength = fast - slow + 1;
                result = S.substr(slow, minLength);
            }
            // shrink the window here
            window[S[slow]]--;
            slow++;
            letterCounter--;
        }
    }
    return result;

  • 0
    P

    What is the runtime you are getting?


  • 0
    P

    +1 vote for nice enhancement


  • 0
    P

    I don't understand this condition: map.find(S[slow]) == map.end(), what's this for? and when this happen, how can we execute window[S[slow]]-- since S[slow] should not exist in both hashmap ?


  • 0
    Q

    Thanks! very inspiring!
    I did a similar approach but I reset "window" every time because I only used a single pointer "fast". After using two pointers ("slow" and "fast") the performance is improved significantly. XD

    # @return a string
    def minWindow(self, S, T):
        if not S or not T: return ''
        
        m = len(T)
        n = len(S)
        if m > n:
            return ''
            
        table = [0]*128
        for i in range(m):
            table[ord(T[i])] += 1
        window = [0]*128
    
        min_len = n
        min_str = ''
        i = 0
        j = 0
        count = 0
        while (i < n):
            if table[ord(S[i])]:
                window[ord(S[i])] += 1
                if window[ord(S[i])] <= table[ord(S[i])]: # !important
                    count += 1
            
            if count >= m: # S[j : i + 1] contains T
                while (not table[ord(S[j])]) or (window[ord(S[j])] > table[ord(S[j])]): 
                # while (the letter is not contained in T or there are extra needed letters to contain T)
                    window[ord(S[j])] -= 1 # dec the count to exact j to i (from 0 to i)
                    j += 1 # find the location of j
    
                if i - j + 1 <= min_len:
                    min_len = i - j + 1
                    min_str = S[j : i + 1]
    
            i += 1 # forward the loop
        
        return min_str

  • 0
    O

    The unordered_map here is very costly. Replace two unordered_maps with two array tables could increase the speed a lot.


  • 0
    Q

    How can you figure out the time complexity is O(N)?


  • 0
    F

    If S[slow] do not exist in map, window[S[slow]] is useless, decreasing the value do not matter


  • 1
    P

    How is this O(n)? You iterate over string S initially with fast index and then once you find the T in the window, you again iterate over S using slow pointer.


  • 0
    P

    I dont think this is O(n) solution. It should be O(n^2)


  • 0
    B

    @PHOTOFT I actually share the same question, O(n^2) is made by the nested for-while loop in some corner case. Hope someone correct me with prof.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.