30. Minimum Window Substring

Hard · String

Given a string `s` and a string `t`, find the minimum window in `s` which will contain all the characters in `t`. If there is no such window in `s` that covers all characters in `t`, return an empty string. If there are multiple such windows, you may return any of them.

Note: If `s` and `t` consist of the same characters in different orders, the entire string `s` is a minimum window.

Examples

Example 1
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" contains all characters from "ABC" (A, B, C). Other valid windows like "ADOBEC" are longer.
Example 2
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string "a" is the minimum window that contains all characters from "a".

Constraints