A word puzzle gives a long string s and a short string t (both lowercase). Find the shortest contiguous part of s that contains every letter of t, counting repeats (if t has two as, the part needs two as).
If several shortest parts exist, print the one that starts first. If none exists, print -.
Constraints
- 1 ≤ |t| ≤ |s| ≤ 100000
- lowercase letters only
Input and output
- Input
- Line 1: s. Line 2: t.
- Output
- The shortest window, or `-`.
Examples
Input 1
dabcaebcd
abdOutput
dab"dab", right at the start, already contains a, b and d.
Input 2
hello
xzOutput
-No window contains x, so print -.
Show hints
- Grow the window to the right until it covers t, then shrink it from the left while it still covers t.
- Keep a count of how many required letters are still missing.
Show the explanation
Count the letters t needs, and a missing total. Move the right end along s, decreasing the need for each letter seen (and missing when it was still needed). Whenever missing hits 0 the window covers t: record it if it is shorter, then move the left end right, giving letters back, until the window stops covering t. Each index enters and leaves once, so the whole scan is O(|s| + |t|).
Original UniCircle question. Last reviewed 22 Oct 2026.