Minimum Window Substring
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 an empty string "".
Example
ADOBECODEBANC ABC
BANC
- Inputs:
s=ADOBECODEBANCis the text to search (positions to ), andt=ABClists the characters a window must contain (here one each). - Where the needed letters sit:
Aat positions and ,Bat and ,Cat and . A valid window covers at least one position from each pair. - Tight windows: only three valid windows cannot be trimmed at either end:
ADOBEC(positions to , length ),CODEBA( to , length ) andBANC( to , length ). Every other valid window, e.g.EBANC(length ), contains one of them plus extra letters. - Output: the shortest is
BANC, length . Dropping its first letter loses theB; dropping its last loses theC. - Duplicates matter: if
theld two copies ofA,BANCwould no longer qualify. If no window coverst, the answer is the empty string.
Constraints
- 1 <= len(s), len(t) <= 10^5
- s and t consist of uppercase and lowercase English letters