Sliding Window Longest or shortest window
174. Minimum Window Substring
You are given two strings, s and t. Return the shortest substring of s that holds every character of
t.
A substring is a block of characters that sit next to each other in s. A substring holds every
character of t when each character appears in it at least as many times as it appears in t. For
t = "aab" the substring needs two as and one b, in any order, and it may hold other characters too.
Every character counts, including spaces and punctuation, and an uppercase letter is a different character
from its lowercase form.
If several substrings share the shortest length, return the one that starts first. If no substring holds
every character of t, return the empty string. Answers are shown in double quotes, so an empty answer
shows as "".
Example 1
Input: s = "the cat sat on a mat", t = "tam"
"mat"Explanation: The only m is at index 17. "mat" adds the a and the t to its right in three characters, while
reaching left to the nearest t, at index 10, takes eight: "t on a m".
Example 2
Input: s = "committee", t = "tmm"
"mmit"Explanation: t needs two ms and one t. "mit" holds only one m, so the answer has to start at the first m.
Example 3
Input: s = "Hello", t = "oh"
""Explanation: s has an uppercase H but no lowercase h, so no substring holds every character of t. The answer
is the empty string.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 1051 ≤ t.length ≤ 105sandthold printable ASCII characters only: letters, digits, punctuation and the space (codes 32 to 126).
Clarifying questions
What you would ask an interviewer before writing any code.