Minimum Window Substring
Explanation & Solution
Description
Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
Examples
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" contains 'A', 'B', and 'C' from string t.
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window, but s only contains one 'a', so return an empty string.
Constraints
1 <= s.length, t.length <= 10^5sandtconsist of uppercase and lowercase English letters.
Approach
Two Pointers pattern
1. Build a Frequency Map of Target Characters
Create a hash map need that counts the frequency of each character in t. This tells us exactly what characters (and how many of each) our window must contain.
2. Initialize the Sliding Window
Set up two pointers, left and right, both starting at index 0. Maintain a window map to track character counts within the current window. Use a have counter to track how many distinct characters have met their required frequency, compared against required (the number of distinct characters in t).
3. Expand the Window by Moving Right
Iterate right across s. For each character added, update the window map. If this character is in need and its count in window now matches the count in need, increment have.
4. Contract the Window by Moving Left
Once have === required, the current window is valid. Record its length if it is the smallest seen so far. Then shrink the window from the left: decrement the count of s[left] in window, and if that causes a needed character to drop below its required count, decrement have. Move left forward and repeat until the window is no longer valid.
5. Return the Result
After processing all characters, if a valid window was found, return the substring from minStart with length minLen. Otherwise, return an empty string.
Key Insight
By tracking how many characters have satisfied their frequency requirement (rather than re-checking all counts each time), we avoid redundant work. Each character is added and removed from the window at most once, giving us an O(n) time algorithm using the sliding window technique with two frequency maps.