Smallest Window Substring

Given two strings s and p, your task is to find the smallest contiguous substring of s which contains all the characters present in p (including multiplicities). This problem is typically solved using a sliding window approach.

For example, if s = "this is a test string" and p = "tist", the smallest window containing all characters of p is "t stri".

In case no such window exists, the program should output an empty string. Note that the order of characters in p is not important, only their counts.

inputFormat

The input is given via standard input (stdin). It contains two lines: the first line is the string s and the second line is the string p.

outputFormat

Print the smallest window substring that contains all characters of p on standard output (stdout). If no such window exists, output an empty string.## sample

this is a test string
tist

t stri