Skip to content
AI360Xpert
Beta
Back to Sliding Window
Difficulty: HardSliding Window

Minimum Window Substring

Problem in Plain English

Given strings s and t, return the shortest contiguous substring of s that contains every character of t with at least the same multiplicity, or the empty string when no such window exists.

Problem Statement

Given strings s and t of lengths m and n, return the shortest contiguous substring of s covering every character of t, including duplicates. Return the empty string when no covering substring exists. Generated test cases guarantee a unique minimum answer.

A substring cannot skip intervening characters. Matching is case-sensitive: A and a are different. With t = "AAB", a window needs two copies of A and one of B; extra letters are allowed. For s = "ADOBECODEBANC" and t = "ABC", ADOBEC qualifies, while DOBE lacks both A and C; the shortest answer is BANC.

Constraints

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

Examples

Example 1

Input
s = "ADOBECODEBANC", t = "ABC"
Output
"BANC"

The window "BANC" holds A, B and C, and no shorter window of s holds all three.

Example 2

Input
s = "a", t = "a"
Output
"a"

The whole string is the only window and it already qualifies.

Example 3

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

The string holds one "a" but two are required, so no window qualifies.

Example 4

Input
s = "ABAAC", t = "AAC"
Output
"AAC"

The final three letters contain two uppercase A copies and one C. AC lacks the second required A, so multiplicity matters.

Example 5

Input
s = "aA", t = "A"
Output
"A"

Only uppercase A satisfies the requirement; lowercase a can be discarded.

Example 6

Input
s = "ABC", t = "D"
Output
""

The whole source lacks D, so a covering window is impossible even though s is longer than t.

Intuition

Imagine stretching a frame over s until it contains all the letter tokens requested by t. Once sufficient, move its left edge inward to discard irrelevant letters and surplus copies. Removing a letter that leaves too few copies makes the frame insufficient again. In ADOBECODEBANC, ADOBEC first covers ABC; dropping its A forces expansion again. Later, EBANC can discard E to become BANC, but cannot discard B. Counts rather than sets preserve repeated requirements.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Hints

Hint 1
Count how many of each letter t needs; a window is valid exactly when it covers every needed count.
Hint 2
Expand the right edge until the window turns valid, then shrink the left edge as far as validity holds: each shrunken-but-valid window is a shorter candidate.
Hint 3
Track validity with two numbers, the distinct letters needed and how many are currently satisfied, so no recount of the whole window is ever required.

Edge Cases

  • s shorter than t: no substring can contain the required number of characters, so return the empty string.
  • Repeated requirements: s = ABAAC with t = AAC returns AAC, containing two A copies.
  • Case sensitivity: s = aA with t = A returns only uppercase A.
  • Absent target letters: s = ABC with t = D returns the empty string despite s being longer.
  • Surplus copies: s = AAAB with t = AAB returns AAB rather than AAAB.
  • Irrelevant gaps remain part of a contiguous answer: s = ABBBBC with t = AC returns the whole string.
  • Whole-string answer: s = a with t = a is recorded before the shrink removes the required letter.
  • Empty inputs are outside the stated constraints. A variant allowing empty t must return the empty string before entering the shrink loop.

Common Mistakes and Interview Tips

  • Comparing sets loses multiplicity: t = AAB needs two A copies, not just the letters A and B.
  • Incrementing have for every needed occurrence overcounts surplus copies. Increment only when its window count reaches exactly need.
  • Using t.length for required instead of its distinct-letter count: AAB has two categories, with requirements 2 and 1.
  • Recording a candidate after removing the left character can save an invalid interval. Update the best before shrinking.
  • Stopping at the first valid interval instead of shrinking while valid misses shorter candidates.
  • Copying every candidate window can introduce repeated slicing costs. Store bestLeft and bestLen and slice the final answer once.
  • Interview tip: the nested shrink loop is linear overall because left advances at most m times and never moves backward.

Key Takeaway

For shortest covering windows, pair the sliding window with satisfied-versus-required counters so validity is maintained incrementally instead of rechecked.