Minimum Window Substring — Hard Coding Interview Question

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return the empty string "". The answer is guaranteed to be unique.

Example

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

Output: "BANC"

Constraints

• m == s.length
• n == t.length
• 1 ≤ m, n ≤ 10⁵
• s and t consist of uppercase and lowercase English letters

Topics & Companies

Topics: strings, sliding-window, hash-map

Asked by: Amazon, Google, Meta, Microsoft, Bloomberg

Optimal Solution Complexity

Time complexity: O(m + n). Space complexity: O(m + n).

Practice more

• All DSA Problems
• DSA Patterns