Minimum Window Substring

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.

-------------------------------- thinking -------------------------------------
In the codes, we should always be careful when comparing (int) with (unsigned int), which might always return false when comparing -1 with (unsigned) 1

https://oj.leetcode.com/discuss/10337/accepted-o-n-solution
https://oj.leetcode.com/discuss/18584/sharing-my-straightforward-o-n-solution-with-explanation
------------------------------- codes -------------------------------------------
   class Solution {
   public:
       string minWindow(string S, string T) {
           unordered_map<char, int> map;
           int map_count=0;

           //initial map
           for (int i = 0; i < T.size(); i++) {
               if (map.find(T[i]) == map.end()) {
                   map[T[i]] = 1;
                   map_count++;
               } else {
                   map[T[i]] += 1;
               }
           }

           int start = 0;
           int end = -1;
           int rst_start = 0;
           int rst_end = -1;
           //bug here -> end < S.size() is wrong, because S.size() is unsigned int, which will always return false when end = -1
           while (end < (int)S.size()) {
               //end increasing, stop when map_count == 0, which means all the characters in T have been found
               while (map_count > 0 && end < (int)S.size()) {
                   end++;
                   if (map.find(S[end]) != map.end()) {
                       map[S[end]]--;
                       if (map[S[end]] == 0) {
                           map_count--;
                       }
                   }
               }
               //start increasing, stop before map_count change to be bigger than 0, which means there are characters missing in T
               while (start <= end) {
                   if (map.find(S[start]) != map.end()) {
                       if (map[S[start]] == 0) {
                           break;
                       } else if (map[S[start]] < 0) {
                           map[S[start]]++;
                       }
                   }
                   start++;
               }
               //update result
               if (map_count == 0 && ((rst_end < 0) || (end - start < rst_end - rst_start))) {
                   rst_end = end;
                   rst_start = start;
               }
               //move start one step ahead
               map_count++;
               map[S[start]]++;
               start++;
           }
           //bug here -> e.g. "a"
           if (rst_end >= rst_start) {
               return S.substr(rst_start, rst_end - rst_start + 1);
           } else {
               return "";
           }
       }
   };

------------------------- codes ----------------------------------------
class Solution {
public:  
    /**
     * @param source: A string
     * @param target: A string
     * @return: A string denote the minimum window
     *          Return "" if there is no such a string
     */
    string minWindow(string &source, string &target) {
        // write your code here
        if (source.size() == 0) return source;
       
        unordered_map<char, int> map;
        for (int i = 0; i < target.size(); i++) {
            if (map.find(target[i]) == map.end()) {
                map[target[i]] = 1;
            } else {
                map[target[i]]++;
            }
        }
        int front = 0;
        int tail = 0;
        int min = INT_MAX;
        int min_tail = -1;
        int cnt = 0;
        while (front < source.size()) {
            bool front_found = false;
            while (front < source.size()) {
                if (map.find(source[front]) == map.end()) {
                    front++;
                } else {
                    map[source[front]]--;
                    if (map[source[front]] == 0) {
                        cnt++;
                    }
                    front++;
                    if (cnt == map.size()) {
                        front_found = true;
                        break;
                    }
                }
            }
            if (front_found) {
                while (tail <= front) {
                    if (map.find(source[tail]) == map.end()) {
                        tail++;
                    } else {
                        //bug here -> tail means the one that shouldn't be deleted from the sub string
                        if (map[source[tail]] == 0) {
                            break;
                        }
                        map[source[tail]]++;
                        tail++;
                    }
                }
                if (min > front - tail) {
                    min = front - tail;
                    min_tail = tail;
                }
            }
        }
        if (min_tail == -1) {
            return "";
        } else {
            return source.substr(min_tail, min);
        }
    }
};