You get two strings, s and t. Find the shortest substring of s containing every character of t, duplicates included. If none exists, return an empty string.
DSA Animator › DSA Revision › Strings › Minimum Window Substring
Remember: grow until valid, shrink while valid. Record the best while shrinking. The video solves Minimum Window Substring (LeetCode 76, Hard) with the Sliding Window pattern from the Strings topic, and you can replay every step in the interactive Minimum Window Substring animation.
You get two strings, s and t. Find the shortest substring of s containing every character of t, duplicates included. If none exists, return an empty string.
s is A D O B E C O D E B A N C, and t is A B C. The shortest window with A, B and C is B A N C. Its length is 4.
Checking every substring is O of n squared or worse. Interviewers expect a linear solution.
Keep a window with two pointers. Grow right until the window covers t. Then shrink from the left to make it smaller. Record the best at every valid window. When a needed character leaves, grow right again. A formed counter tracks how many characters of t are covered.
Right moves over A, D, O, B, E and C. At C, the window A D O B E C covers t: length 6, the first best. Removing A breaks it. Right moves on to the A at index 10. Valid again, but length 10. Shrinking past D, O, B and E keeps it valid, because another B is ahead. C O D E B A has length 6, not smaller. Removing C breaks it again. Right reaches the C at index 12. Removing O and D leaves E B A N C, length 5, a new best. Removing E leaves B A N C, length 4, even better. Removing B breaks it, and right is at the end. The answer is B A N C.
In code, count t, and required, its number of distinct characters. Right adds a character, and formed rises when a count is complete. While formed equals required, update the best and remove the left character. If that character was needed, formed drops and the loop stops. Each character is touched at most twice, so it is O of n time.
Remember: grow until valid, shrink while valid. Record the best while shrinking.