SDE Path

Minimum Window Substring

Hard

Minimum Window Substring

Find the smallest substring of one string that contains all characters of another string.

Input format

The first line contains string S. The second line contains string T.

Output format

Print the smallest window in S containing all characters of T (with multiplicity). If multiple windows of the same length exist, return the leftmost. If none exist, return -1.

Constraints

  • Values fit in a 64-bit signed integer
  • Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

Sample cases

Example 1
Input
ADOBECODEBANC ABC
Expected output
BANC
Example 2
Input
a a
Expected output
a