Skip to content
BASA DSA

Minimum Window Substring

HardSliding Window

Return the shortest substring of s containing every character of t with its required multiplicity. Return an empty string if impossible.

Example 1

Input
s = "xxABCAy"
t = "AABC"
Output
"ABCA"

Explanation

ABCA contains two A letters, one B and one C; every shorter window misses an occurrence.

Example 2

Input
s = "abc"
t = "zz"
Output
""

Explanation

No z occurs in abc, so no valid window exists.

Example 3

Input
s = "aa"
t = "aa"
Output
"aa"

Explanation

Both a occurrences are required, so the whole source is the shortest window.

Constraints

  • 1 <= string lengths <= 100000
  • Strings contain English letters
  • The shortest valid window is unique when one exists

Function contractminWindowArguments: json, json
Loading draft…
SolutionRuns on your device