Minimum Window Substring

Hard

sliding-windowstringhash-table

Given strings s and t, return the minimum-length substring of s that contains every character of t (including duplicates). If no such window exists, print an empty line. The answer is guaranteed unique.

Input

Line 1: string s
Line 2: string t

Output: the minimum window, or empty output if none.

Example 1

Input:

ADOBECODEBANC
ABC

Output:

BANC

Example 2

Input:

a
a

Output:

Example 3

Input:

a
aa

Output:

Two 'a's are required but only one exists.

Constraints

1 ≤ s.length, t.length ≤ 10^5
English letters (upper and lower case).

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Minimum Window Substring

Hard

sliding-windowstringhash-table

Input

Line 1: string s
Line 2: string t

Output: the minimum window, or empty output if none.

Example 1

Input:

ADOBECODEBANC
ABC

Output:

BANC

Example 2

Input:

a
a

Output:

Example 3

Input:

a
aa

Output:

Two 'a's are required but only one exists.

Constraints

1 ≤ s.length, t.length ≤ 10^5
English letters (upper and lower case).

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.