Asked at

Minimum Window Substring

Hard
VerifiedStringSliding WindowHash Map~35 min

Given strings s and t, return the smallest substring of s that contains every character of t, counting multiplicity. Return "" if no such window exists.

Grow a window to satisfy the demand, then shrink it from the left while it stays valid, recording the shortest seen. The input arrives as a single object { s, t }.

Examples

in{ s: "ADOBECODEBANC", t: "ABC" }
out"BANC"

"BANC" is the shortest window containing A, B, and C.

in{ s: "a", t: "a" }
out"a"

The whole string is the only window.

Constraints

  • 1 ≤ s.length, t.length ≤ 10⁵
  • s and t consist of uppercase and lowercase English letters.
  • The answer is unique for every test case here.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.