Minimum Window Substring

Given two strings s and t, find the minimum window in s which will contain all the characters in t (including duplicates). If there is no such window in s that covers all characters in t, return an empty string.

This is a classical sliding window problem. The goal is to minimize the length of the window while ensuring that for every character c in t, the window has at least as many occurrences of c as in t. Mathematically, if we denote the frequency of a character c in t as \(f_t(c)\), then for any valid window \(w\) in s, we require:

\[ \forall c,\quad f_w(c) \ge f_t(c). \]

Your task is to implement the function to determine this substring by reading input from stdin and writing the result to stdout.

inputFormat

The input consists of two lines. The first line contains the string s and the second line contains the string t.

outputFormat

Output the minimum window substring of s which contains all characters from t. If no such substring exists, output an empty string.## sample

ADOBECODEBANC
ABC

BANC