Given strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included. Return "" if no such window exists.
s = "ADOBECODEBANC", t = "ABC""BANC"s
need map from t. needed = unique chars in t.have. If have[c]==need[c] → formed++have. If have[c]<need[c] → formed--. l++formed counter: Instead of scanning all of need every step, formed increments only when have[c] exactly reaches need[c]. One counter replaces a full map comparison.
Expand → Shrink cycle: We expand R until all chars are satisfied, then shrink L to find the minimum valid window. Two-pointer guarantees each character is visited at most twice — O(n) total.
Why variable window? Unlike fixed windows, the valid size varies. We don't know the answer length upfront — the window grows and shrinks dynamically based on the contents of t.
Checking every substring is O(n²) 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.
Grow until valid, shrink while valid. Record the best while shrinking.
Run the animation above on your own input, or watch the 1:48 video explanation of Minimum Window Substring with a dry run and Java code.