Min Prompt Span Cover
A retrieval system has a long token stream and a set of required keyword tokens that a good context snippet must all contain. To keep the prompt short, find the smallest contiguous span of the stream that covers every required token (counting multiplicities). Under the hood this is the classic minimum-window-substring.
Problem
Given a string s and a string t, return the smallest substring of s that contains every character of t including duplicates. If no such window exists, return the empty string.
Input
Strings s (length n) and t (length m), 1 ≤ n, m ≤ 10^5, ASCII characters.
Output
The minimum-length covering substring, or "" if none exists.
Constraints
- 1 ≤ n, m ≤ 100,000
- Character multiplicities in t must be fully covered
- If multiple minimal windows tie, return the leftmost
Examples
Example 1
Input
s = "ADOBECODEBANC", t = "ABC"
Output
BANC
"BANC" is the shortest span containing A, B and C.
Example 2
Input
s = "a", t = "a"
Output
a
The single character already covers the requirement.