题目内容

给定两个字符串 s 和 t。如果 s 的某个连续子串满足：对于 t 中出现的每一种字符，该子串中该字符的出现次数都不少于 t 中的出现次数，则称该子串能够覆盖 t。请找出 s 中能够覆盖 t 的长度最小的连续子串并返回。如果 s 中不存在能够覆盖 t 的子串，则返回空字符串 ""。

约束条件：两个字符串的长度均在 $1$ 到 $10^5$ 之间，且仅由英文字母组成，题目数据保证如果存在解，答案唯一。

输入描述

输入包含两个参数：字符串 s 和字符串 t，其中 s 是待搜索的字符串，t 是需要被覆盖的目标字符串。

输出描述

返回一个字符串，表示 s 中能够覆盖 t 的最短连续子串；若不存在这样的子串，则返回空字符串 ""。

样例1

输入

ABBCDA
ABCD

输出

BCDA

说明

目标串 t 需要 1 个 A、1 个 B、1 个 C 和 1 个 D。在 s = "ABBCDA" 中，子串 "BCDA" 位于索引 2 到 5，长度为 4，正好包含这四种字符各 1 次。

由于 t 中有 4 种不同字符，任何长度小于 4 的子串都不可能覆盖 t，因此 "BCDA" 是最短覆盖子串。

样例2

输入

xabac
aab

输出

aba

说明

目标串 t = "aab" 要求子串中至少包含 2 个 a 和 1 个 b。在 s = "xabac" 中，子串 "aba" 从索引 1 到 3，包含 2 个 a 和 1 个 b，长度为 3。

字符 x 和末尾的 c 不在 t 中，不影响覆盖条件。其他包含所需字符的候选子串长度更长，因此最短为 "aba"。

样例3

输入

a
b

输出

说明

目标串 t = "b" 要求包含字符 b，但 s = "a" 中完全没有 b。因此不存在任何子串能覆盖 t，根据题意返回空字符串 ""。