Given two strings S and T, find the smallest (contiguous) substring of S that contains all characters of T (including duplicates). If no such substring exists, output an empty string.
Input (stdin)
S
T
1 ≤ |S|, |T| ≤ 10^5Output (stdout)
substring
If multiple minimum windows exist, output the one that appears first in S. If none exists, output an empty line.
Input
adobecodebanc
abc
Output
banc
Explanation
The substring "banc" is the shortest window of S that contains a, b, and c.
The classic minimum window substring problem is solved efficiently with a sliding window and a frequency map.
Example 1
Input: adobecodebanc abc
Output: banc
The window "banc" contains a, b, c and is the shortest possible.
Example 2
Input: a aa
Output:
String S does not contain enough 'a' characters.
Constraints
Hints
Given two strings S and T, find the smallest (contiguous) substring of S that contains all characters of T (including duplicates). If no such substring exists, output an empty string.
Input (stdin)
S
T
1 ≤ |S|, |T| ≤ 10^5Output (stdout)
substring
If multiple minimum windows exist, output the one that appears first in S. If none exists, output an empty line.
Input
adobecodebanc
abc
Output
banc
Explanation
The substring "banc" is the shortest window of S that contains a, b, and c.
The classic minimum window substring problem is solved efficiently with a sliding window and a frequency map.
Example 1
Input: adobecodebanc abc
Output: banc
The window "banc" contains a, b, c and is the shortest possible.
Example 2
Input: a aa
Output:
String S does not contain enough 'a' characters.
Constraints
Hints