Minimum Window Substring

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

The problem can be formally stated as follows:

Let \( s \) be a string of length \( n \) and \( t \) a string of length \( m \). Find the smallest substring \( s[i \dots j] \) such that for every character \( c \) in \( t \), the frequency of \( c \) in \( s[i \dots j] \) is at least the frequency of \( c \) in \( t \). If no such substring exists, return the empty string.

Example:

• Input: s = "ADOBECODEBANC", t = "ABC"
• Output: BANC

inputFormat

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

outputFormat

Output a single line containing the minimum window substring of s that contains all characters in t. If no such substring exists, output an empty string.

ADOBECODEBANC
ABC

BANC