Jan 12, 2021
Find the minimum length substring in s that will cover all the characters in t.
Represent three states of the problem:
zero: just meet the needs
negative: extra or not needed
1. Use an array/list of size 128 to represent all types of characters and initialize the array with zeros.
2. Create the characters to count mapping using the array above.
3. Loop thru the string s.
if current char in the mapping is greater than 0 meaning that current char is needed, so decrement the need and the char count by 1, otherwise only decrement the char count by 1.
while the need is zero, we have fulfilled all the needs or have found the window. Then we can go ahead update the length of the current substring. Now we need to shrink the window on the left side, to see if the window can be smaller and still meets the need[need == 0], because some char may be more than enough or extra.
If excluding the left char of the the window makes the char in the mapping greater than zero or become positive, it indicates that the left char is needed, thus we need to increment the need by 1.
4. return the min substring
Time: O(size of s).