PythonHardSliding Window35 min
Find the minimum covering substring
Compare exact ASCII characters. Break equal-length ties by earliest starting index; return an empty string if t is empty or no window exists. Interviewers use this problem to assess expand until all multiplicities are covered, then shrink while valid.
Input
Two lines: s followed by t.
Output
Print the result on one line; print an empty line for an empty string.
Constraints
0 <= each length <= 100000.
Example
Input
ADOBECODEBANC ABC
Output
BANC
Example 2 input
abxxba ab
Output
ab
Equal-length windows choose the first occurrence.
Public test cases (2)
Input
ADOBECODEBANC ABC
Expected output
BANC
Input
aaab aab
Expected output
aab
Hints (2)
- Identify the state needed to avoid repeated work.
- Expand until all multiplicities are covered, then shrink while valid.
Target complexity: time O(n + m) · space O(k), excluding the output substring