Minimum Window Substring

Hard · Sliding Window

You are given two strings s and t. Find the shortest contiguous substring of s that contains every character of t at least as many times as it appears in t. If no such substring exists, return an empty string. Assume there is at most one valid answer of minimum length.

Examples

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Why:    "BANC" is the shortest substring of s that contains an 'A', a 'B', and a 'C'.

Input:  s = "a", t = "a"
Output: "a"
Why:    The whole string already matches t exactly.

Input:  s = "a", t = "aa"
Output: ""
Why:    s only has one 'a' so it can never contain two copies of 'a'.

Constraints

1 <= s.length, t.length <= 10^5, s and t consist of uppercase and lowercase English letters

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Minimum Window Substring

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Minimum Window Substring. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.