2074: 最小复盖子串

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：10 Solved：3

Description

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

 注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 

示例 ：
输入：s = "ADOBECODEBANC"  t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。


Input

输入第一行为字符串 s ， 第二行为字符串 t 。

Output

输出 s 中涵盖 t 所有字符的最小子串。

Sample Input Copy 

ADOBECODEBANC
ABC

Sample Output Copy 

BANC

HINT

  • 1 <= s 和 t 的字符长度 <= 105
  • s 和 t 由英文字母组成