Minimum Window Substring

Given two strings s and pattern, the task is to find the smallest (minimum length) contiguous substring in s that contains all the characters of pattern (including duplicates). If there is no such substring, output an empty string.

The problem can be formalized as follows: $$\text{Find } s[i:j] \text{ such that } \forall c \in pattern, \; count(s[i:j], c) \ge count(pattern, c) \quad,\quad 0 \leq i \leq j < |s|$$

This problem is typically solved using the sliding window approach. The complexity requirement of an optimal solution is O(n), where n is the length of s.

inputFormat

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

• The first line contains the string s.
• The second line contains the pattern string pattern.

outputFormat

Output to standard output (stdout) a single line which is the minimum window substring of s that contains all the characters of pattern. If no such window exists, output an empty string.

ADOBECODEBANC
ABC

BANC