[Leetcode Solution] Minimum Window Substring

Analysis

• O(n) complexity, the first touch is of course the two pointers. 
• Use two pointers to scan the string only one pass and dynamic update the status.
• Say two pointers p and q. Let the substring between p and q is the required window. At the beginning p and q are equal to 0
• If the formed window does not contain string T, then move pointer q forward until the window contains string T.
• If the q reaches the end of string however still not contain T, then return false
• If window already contains the T, move pointer p forward to minimum the size of window. Move pointer p until it is the minimum window that still contains T
• Use a hash table to (C++ map) to count the number of each char appeared in T. If the char pointed by p has more number in map then that char appeared in T, then move forward p.

Note

• The method count of set, map is only used to test if the element reside in the container rather then the number of reside. Thus the return value of count is always 0 or 1.
• Always remember if you want to access a key in a set, if that key is not in the set or map, the access method will insert this key into the set. This might lead to vital fault. So before access a key in set, remember check if it is in the set using count. Otherwise error might occur just like access a null pointer

Code

UPDATED AT LEETCODE 2ND PASS