Minimum Window Substring

Hard

Sliding Window

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 "".

The testcases will be generated such that the answer is unique.

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: The minimum window substring "BANC" includes "A", "B", and "C" from string t.

Example 2

Input: s = "a", t = "a"

Output: "a"

Explanation: The entire string s is the minimum window.

Example 3

Input: s = "a", t = "aa"

Output: ""

Explanation: Both "a"s from t must be included in the window. Since s only has one "a", return empty string.

Constraints

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

Show Hints (3)

Hint 1: Use two pointers to create a sliding window.

Hint 2: Use a hash map to count characters needed from t.

Hint 3: Expand the window until all characters are found, then contract to find minimum.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?