Minimum Window Substring
HardSliding Window · Airbnb
You are given two strings s and t. Find the shortest substring of s (a contiguous run of characters) that contains every character of t, including duplicates: if t contains a character c three times, the substring must contain c at least three times. The substring may contain extra characters as well, and the order of characters does not matter.
Return that shortest substring. If no substring of s covers t, return the empty string "".
Matching is case-sensitive (A and a are different). The tests are built so that, when an answer exists, exactly one shortest substring exists.
Example 1
- Input:
- s = "cabwefgewcwaefgcf", t = "cae"
- Output:
- "cwae"
- Explanation
- Windows such as
cabwecontainc,aande, but the shortest one iscwae(length 4), where the needed characters sit closest together.
Example 2
- Input:
- s = "xaybxa", t = "aa"
- Output:
- "aybxa"
- Explanation
tneeds twoacharacters. The only window holding both isaybxa, so the extra letters between them must be included.
Example 3
- Input:
- s = "aaflslflsldkalskaaa", t = "aaz"
- Output:
- ""
- Explanation
- There is no
zanywhere ins, so no window can covertand the answer is the empty string.
Constraints
- 1 ≤
s.length,t.length≤ 105 sandtcontain uppercase and lowercase English letters- When a covering substring exists, the shortest one is unique