Find the minimum covering substring
Print the shortest source substring containing every target character with its multiplicity. Break ties by earliest start; print an empty line when target is empty or no window exists. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe algorithm selection, invariants, and boundary handling.
Input
Two lines: source, then target. Both may be empty.
Output
Print the shortest source substring containing every target character with its multiplicity. Break ties by earliest start; print an empty line when target is empty or no window exists.
Constraints
ASCII letters only; each line length <= 100000.
Example
Input
ADOBECODEBANC ABC
Output
BANC
Example 2 input
abxba ab
Output
ab
This example exercises earliest-start tie-breaking.
Public test cases (2)
Input
ADOBECODEBANC ABC
Expected output
BANC
Input
aa aa
Expected output
aa
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Track remaining character requirements while expanding right, then shrink left whenever the window covers the target.
Target complexity: time O(n+m) · space O(1), ASCII alphabet