Minimum Window Substring

Given two strings S and P, your task is to find the minimum contiguous substring of S which contains all the characters of P (including duplicates).

If there is no such window in S, output an empty string "".

This problem can be efficiently solved using a sliding window algorithm that operates in \(O(n)\) time in practice.

Examples:

• For S = "this is a test string" and P = "tist", the minimum window is "t stri".
• For S = "geeksforgeeks" and P = "ork", the minimum window is "ksfor".

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains the string S, and the second line contains the string P. Both strings are composed of ASCII characters.

outputFormat

Output to standard output (stdout) the minimum window substring of S that contains all the characters in P. If no such substring exists, output an empty string.## sample

this is a test string
tist

t stri