Description
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.
Examples
Input:
s = "ADOBECODEBANC", t = "ABC"Output:
"BANC"Explanation:
Sliding window finds BANC (indices 9-12) containing A,B,C with length 4, shorter than ADOBEC.
Input:
s = "a", t = "a"Output:
"a"Explanation:
String a exactly matches target a. Window cannot be smaller than the target itself.
Input:
s = "a", t = "aa"Output:
""Explanation:
Target aa needs 2 as but source a has only 1. No valid window exists.
Constraints
- •
m == s.length - •
n == t.length - •
1 ≤ m, n ≤ 10⁵ - •
s and t consist of uppercase and lowercase English letters.