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 "".

Note: If there is such a window, it is guaranteed that there will always be only one unique minimum window substring.

The problem can be formally formulated as: find indices \(i\) and \(j\) (with \(0 \le i \le j < |s|\)) such that the substring \(s[i..j]\) contains every character from t at least as many times as it appears in t, and \(j-i+1\) is minimized. We use the notation \( |s| \) to denote the length of s.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains the string s.
2. The second line contains the string t.

Both strings consist only of printable ASCII characters.

outputFormat

Output to standard output (stdout) a single line containing the minimum window substring of s that contains all the characters (with correct counts) of t. If no such window exists, output an empty string.

ADOBECODEBANC
ABC

BANC