Minimum Window Substring

In this problem, you are given two strings s and t. Your task is to find the minimum window (substring) 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: The solution should use an efficient sliding window approach. One possible hint for the algorithm is to maintain a frequency counter for the characters of t and use two pointers to adjust the current window in s.

The problem can be mathematically formulated as finding indices l and r such that for every character c in t, [ \text{count}_{s[l...r]}(c) \geq \text{count}_t(c) ] and the length r - l + 1 is minimized.

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 that contains all characters from t. If no such window exists, output an empty string.## sample

ADOBECODEBANC
ABC

BANC