This visualization was generated by AI and may contain errors. Please verify with the official LeetCode problem #76.
Find the smallest substring of s that contains all characters from t using the sliding window technique.
Given two strings s and t of lengths m and n respectively,
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 "".
The testcases will be generated such that the answer is unique.
A substring is a contiguous sequence of characters within the string.
Use a sliding window with two pointers. Expand the window by moving the right pointer until all
characters from t are included. Then shrink from the left to find the minimum window.
Track character counts using a hash map to efficiently check if all required characters are present.
need for characters in t.
Track missing count (total characters needed).right pointer through s. For each character,
decrement its count in need. If count was positive, decrement missing.missing == 0 (all characters found), try shrinking from left.
Update the best window if current is smaller.s[left] in need. If it becomes positive,
increment missing (character now needed again). Move left forward.| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m + n) | Each character in s is visited at most twice (once by right, once by left pointer). Creating the need map takes O(n). |
| Space | O(k) | k is the number of unique characters in t. The need hash map stores at most k entries. |