For this problem, we take use of the sliding window.
First we should search characters from the start in order to get the first substring which contains t.
In the example, the first string we get is "ADOBEC"
You may ask how can we know whether it reaches a substring that contains all the letters in T. The answer is to use a HashMap and an Integer matchCount. Why we use the hashMap? Because we can keep track of which letter is lacked or has already been fulfilled. For example: You have a substring AB, and the next letter is "B", if you only use an integer to judge whether the substring is fulfilled, it will return true. since ABB = 3 which is the length of ABC.
We need a hashMap for t and for the current substring we have, in order to compare the occurrence of the letters. Once the substring is ensured to contain t, we can try to shrink the substring from the left side to see whether it still contains t. For instance, AABC contains ABC, and ABC also contains ABC.
If it's true, then we continuously move the left pointer to shrink the substring, if it's false, we move the right pointer to find a fulfilled substring.
We iterate the whole process until the right pointer reaches the end. and left pointer moves to the rightmost it can reach.
In summary, the whole process would be:
1. record the letter occurrence of t in a hashmap hm
2. set left and right pointer to 0， initialize a new map called actualhm which records the current substring letter occurance, initialize a count to record whether all letter is fulfilled(when it equals to t.length()).
3. From left = 0, right = 0, move the right pointer. At each move, check whether the current occurrence is in hm, if so, we increase the letter count by 1, and if the actual letter count is not beyond the letter count in hm, we increase matchCount by 1, which means we fulfill the final condition by one.
4. when matchCount = t.length, it means we fulfill the condition. We first record the substring if it's shorter than what we have recorded, then we try to move the left pointer to right, and decrease the letter count in actual hm and decrease the matchCount(If actualhm.count <= hm.count). If the substring after move still fullfill, we keep moving left pointer to right. if not, we end the loop and return back to add the t pointer.
5. After the right pointer reaches the end and left pointer interactively find the rightmost position, we can return our result. Because we set the default value to "", we can directly return it. However, we need to add if(result == "") then record current substring at (matchCount == t.length) so that we don't skip the condition.
Code:
