Minimum Window Substring

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 \) in complexity \( O(n) \). If there is no such window in \( s \) that covers all characters in \( t \), return an empty string "".

Note:

• When there is a valid window, there will always be only one unique minimum window.
• Characters in \( t \) are considered with their multiplicities. For instance, if \( t = \"AABC\" \) then the window must contain two 'A's, one 'B', and one 'C'.

Example 1:

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

Example 2:

Input:
  s = "a"
  t = "a"
Output:
  "a"

Example 3:

Input:
  s = "a"
  t = "aa"
Output:
  ""

inputFormat

The input consists of two lines:

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

Both strings consist of uppercase/lowercase English letters.

outputFormat

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

## sample

ADOBECODEBANC
ABC

BANC