Smallest Substring with All Characters

Given two strings A and B, find the smallest contiguous substring of A that contains all the characters present in B, including their respective counts. If no such substring exists, return an empty string.

The problem can be formalized using the following criteria:

Let \(A\) and \(B\) be two strings. Find the minimum length substring \(S\) of \(A\) such that for every character \(c\) in \(B\), the count of \(c\) in \(S\) is at least as much as in \(B\). Otherwise, return an empty string.

Example:

• Input: A = "adobecodebanc", B = "abc"
• Output: "banc"

Note: If multiple answers exist, the substring with the smallest starting index is acceptable as long as its length is minimal.

inputFormat

The input consists of two lines. The first line contains the string A and the second line contains the string B.

outputFormat

Output a single line containing the smallest substring of A that contains all the characters from B. If there is no valid substring, output an empty string.

adobecodebanc
abc

banc