Go over the blog and implementation in the blog - write down the idea, learn the thinking process.

FindMinimumSubstringContainString.cpp

/*
Feb.23, 2018
What Julia likes to do is to go over the analysis word by word, and then learn the thinking process. 

Source code is from the blog:
http://www.cnblogs.com/lichen782/p/leetcode_minimum_window_substring_3.html

Problem statement:
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".

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.

Analysis the algorithm:
前面两个系列讲了O(N*M)和O(NlogM)的解法。下面讲一下O(N)的。
There are two solutions with time complexity O(N*M) and O(NlogM). Here the algorithm is with time complexity O(N). 

Please take a look at the leecode discussion panel here: 
https://leetcode.com/problems/minimum-window-substring/discuss/

using an example to explain the algorithm:
"acbbaca"
T = "aba"

First substring containing all chars in T:
"acbba"
Left point is 0 and right point is 4. 

Since the left pointer cannot be moved, since char 'a' needs two of them in T string. Otherwise the substring is 
not valid one. 

"acbbaca" is the second substring containing all chars in T string. But 'a' NeedToFind['a] = 2, but hasFind['a'] = 3, 
so the left pointer is moved to reduce the hasFind['a' = 2. 
The substring is "bbaca"
We also like to skip those chars not in T string, such as char 'c' which is not in "aba". 
There is still one redundant 'b' in the substring "bbaca". 

begin和end都最多前进N次，从而整个算法执行小于2N. 复杂度是O(N)。

*/

public String minWindow3(String S, String T){
         HashMap<Character, Integer> needToFill = new HashMap<Character, Integer>();
         HashMap<Character, Integer> hasFound   = new HashMap<Character, Integer>();
         
         int count = 0;
         for(int i = 0; i < T.length(); i++){
             if(!needToFill.containsKey(T.charAt(i)))
             {
                 needToFill.put(T.charAt(i), 1);
                 hasFound.put(T.charAt(i), 0);
             }
             else {
                 needToFill.put(T.charAt(i), needToFill.get(T.charAt(i)) + 1);
             }
         }
         
         int minWinBegin = -1;
         int minWinEnd = S.length();
         for(int begin = 0, end = 0; end < S.length(); end++)
         {
             char c = S.charAt(end);
             if(needToFill.containsKey(c)){
                 hasFound.put(c, hasFound.get(c) + 1);
                 if(hasFound.get(c) <= needToFill.get(c)){
                     count++;
                 }
                 
                 if(count == T.length()){
                     while(!needToFill.containsKey(S.charAt(begin)) ||
                           hasFound.get(S.charAt(begin)) > needToFill.get(S.charAt(begin))) 
                     {
                         if(needToFill.containsKey(S.charAt(begin)) 
                                 && hasFound.get(S.charAt(begin)) > needToFill.get(S.charAt(begin)))
                         {
                             hasFound.put(S.charAt(begin), hasFound.get(S.charAt(begin)) - 1);
                         }
                         
                         begin++;
                     }
                     
                    if(end - begin < minWinEnd - minWinBegin){
                         minWinEnd = end;
                         minWinBegin = begin;
                     }
                 }
             }
       }
       
       return minWinBegin == -1 ? "" : S.substring(minWinBegin, minWinEnd + 1);