← 返回 meta 的题目列表Sliding Window String Problem (Variant)
类型：online_judge
Given two strings s and t, find the shortest contiguous substring of s that contains all characters in t (including multiplicities). If no such substring exists, return an empty string.
Input: two lines, s and t
Output: the shortest valid substring, or an empty line if none
Goal: close to O(|s|) time
Example
Input:
ADOBECODEBANC
ABC
Output:
BANC
Constraints
1 <= |s|, |t| <= 2e5
Character set is ASCII or lowercase letters (confirm in interview)
Example
Input
ADOBECODEBANC
ABC
Output
BANC