v9.1.1
Menu

Minimum Window Substring

hardPROArrays & StringsGoogle DSA

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 there is no such substring, return an empty string "".

Example

Input
ADOBECODEBANC
ABC
Output
BANC
Reasoning
  • Inputs: s = ADOBECODEBANC is the text to search (positions 00 to 1212), and t = ABC lists the characters a window must contain (here one each).
  • Where the needed letters sit: A at positions 00 and 1010, B at 33 and 99, C at 55 and 1212. A valid window covers at least one position from each pair.
  • Tight windows: only three valid windows cannot be trimmed at either end: ADOBEC (positions 00 to 55, length 66), CODEBA (55 to 1010, length 66) and BANC (99 to 1212, length 12−9+1=412 - 9 + 1 = 4). Every other valid window, e.g. EBANC (length 55), contains one of them plus extra letters.
  • Output: the shortest is BANC, length 44. Dropping its first letter loses the B; dropping its last loses the C.
  • Duplicates matter: if t held two copies of A, BANC would no longer qualify. If no window covers t, the answer is the empty string.

Constraints

  • 1 <= len(s), len(t) <= 10^5
  • s and t consist of uppercase and lowercase English letters

More from Google DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.