We will use LeetCode 76 minimum window substring as an example for the sliding window kinds of problem analysis.
Sliding Window questions go like this:
there will be 2 pointers. First, the left pointer does not move, the right pointer keep going until it finds the first substring(or whatever) that fits with what we are looking for.
In the case of LeetCode #76, we first keep going until we find the first substring that contains “ABC”
A D O B E C O D E B A N C
left pointer: 0 (A) right pointer: 6(C)
When we found the substring that fits with the requirement, we will start moving the left pointer towards the right direction to see if doing so will break the requirement (in this case, it will) and if it does then record the initial left pointer position and the length of the substring we just had that fits with the requirement.
After we realize we break the requirement then the right pointer keep moving towards right until we finds another substring that fits with the requirement.
A D O B E C O D E B A N C
left pointer: 1(D) right pointer: 10(A)
and then we start moving left pointer again to see where it can move to without breaking the requirement which in this case it will move to 6 without breaking the requirement. We compare the length with the last one we recorded, realized this is shorter so we record the new starting index and length. We keep doing the same until the right pointer reach the end of the string and we return the shortest substring we find.
Another implementation detail to pay attention on this specific question is how we know we found all the characters? notice that we need to count duplicates too. for example if the target string is AABC then we can only return a substring if it has 2 As in it too. The way to do it is to use a HashMap and count the number of times we need to find them. And each time we find a character that is in the HashMap we decrease the value by 1. When the number hit 0 that means we reach the frequency we need for this character and we can add 1 to the number of character that reaches requirement. For example if we finds 2A then we add 1 to total count of characters that reaches requirement. And when that count is the same as the size of the dictionary then we know we have fulfill the requirement.
