Minimum Window Substring

Reported in interviews at Citadel Jane Street Two Sigma Meta

Problem statement

Given a string $S$ of length $m$ and a string $T$ of length $n$, find the shortest contiguous substring of $S$ that contains every character in $T$ (including duplicates). If no such substring exists, return the empty string. If there are multiple windows of the same minimum length, return the one that appears first (leftmost).

Constraints:

  • $1 \le m, n \le 10^5$
  • $S$ and $T$ consist of uppercase and lowercase English letters
  • $T$ may contain duplicate characters, and the window must include at least that many copies of each

Example 1:

  • Input: $S = $ "ADOBECODEBANC", $T = $ "ABC"
  • Output: "BANC"
  • Explanation: The substring "BANC" starting at index 9 contains A, B, and C and has length 4. Earlier windows like "ADOBEC" (length 6) also contain all characters but are longer.

Example 2:

  • Input: $S = $ "a", $T = $ "a"
  • Output: "a"

Example 3:

  • Input: $S = $ "a", $T = $ "aa"
  • Output: ""
  • Explanation: $T$ requires two as but $S$ only has one, so no valid window exists.

Design an algorithm that runs in $O(m + n)$ time.

Show hint

Which technique lets you examine every candidate substring without restarting from scratch each time the starting position changes?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems