Skip to main content

76. Minimum Window Substring

hard

Find the shortest substring of s that contains every character of t (multiplicities included). The textbook sliding-window-with-frequency-map question and a common bar-raiser at top tech companies.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 test cases will be generated such that the answer is unique.

Constraints

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

Examples

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"

Example 3

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

Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', no valid windows exist.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Build a need-count map for t: how many of each character does the window have to contain?

Hint 2

Expand a window with right until you have all required characters. Then shrink from left as long as the window stays valid, tracking the minimum.

Hint 3

Track 'have' (number of unique characters whose count in the window meets the need) and compare with 'required' (number of unique characters in t).

Solution approach

Reveal approach

Sliding window with two frequency maps and a have/required counter. Build need = char-count map of t and required = number of unique keys in need. Track windowCounts (counts inside the current window) and have = number of unique chars whose windowCount equals need's count. Sweep right: include s[right] in windowCounts; if the char is in need and its count matches need[c], increment have. While have == required, this is a valid window — update the best answer and shrink: decrement windowCounts[s[left]], and if it was in need and its count drops below need[c], decrement have. Advance left. At the end, return the best substring (or empty string if none). O(m + n) time, O(unique chars in t) space.

Complexity

Time
O(m + n)
Space
O(k)

Related patterns

  • sliding-window
  • hash-map
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Microsoft
  • Uber
  • Airbnb

Practice these live with InterviewChamp.AI

Drill Minimum Window Substring and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →