[Leetcode] Minimum Window Substring

Problem 

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.

Algorithm

Similar to Longest Substring without Repeating Characters, see here. 

In order to check whether a character appears in string T in O(1) time, initially, we build a hash map dictionary.

 <key, value> = <character in T, number of occurrence in T>

Maintain a substring window [L, R] in S. Move R forward,  until the window contains all characters in T. For each character c in the S,  if it is not in the dictionary, continue. Else if the current character is in the dictionary, based on its value in the hash map, we have

1. value > 0, number of c is less than needed. 
2. value = 0, number of c is exactly as needed
3. value < 0, number of c is more than needed.

Since, we find a c, we update the hash map. Once all keys in hash map has non-positive values, we found a window containing all characters in T. This window is not optimal, some characters are more than needed. We can shrink the window's left boundary, if we see a unneeded character, or a redundant character. 

Finally, checking the values of each keys are expensive. Instead, maintaining a total count of needed characters can reduce this loop up time.  

Code