Cover every required character
Updated
Build need[] from t. missing starts at the number of required units. Expand R: if --need[s[R]] >= 0, missing--. When missing==0 the window covers. Then shrink while missing stays 0, and track min length.
What to focus on
Cover means window count ≥ need for every character in t. Expand until missing==0, shrink while still covering. Extra copies (need goes negative) let you drop the left copy.
Worked examples
classic
s = "ADOBECODEBANC", t = "ABC"- expand until missing==0 at R=5 "ADOBEC"
- shrink drops A, missing=1
- later missing==0 again, shrink to L=9 R=12
Result: "BANC" length 4
later shorter
s = "abca", t = "ac"- expand to "abc" missing==0 len 3
- drop a missing=1
- R=3 a restores, window "bca"
- drop b still covers "ca"
Result: "ca" length 2
whole needed
s = "abca", t = "abc"- "abc" covers len 3
- add last a, shrink first a, "bca" still covers len 3
Result: min length 3
Try it
Write minCover(s, t). s is the source string. t is the requirement string. L is the left index. R is the right index. The window includes s[L..R]. Cover means every character of t is present in enough copies. Return the shortest covering slice. Trace missing on ADOBECODEBANC vs ABC to BANC, abca vs ac to ca, abca vs abc to length 3.
s and t are nonempty. s contains at least one covering of t.