Covering window has a requirement map
Updated
t becomes need[ch] = count of ch in t. missing is how many need units are still unfilled. The window is variable length: grow until missing==0, shrink while need stays satisfied.
What to focus on
need[ch] going negative means extra copies of ch. Those extras are what let L advance without breaking cover. This is not a fixed-length anagram window.
Worked examples
need ABC
s = "ADOBECODEBANC", t = "ABC"- need {A:1,B:1,C:1}, missing=3
- each first A,B,C decrements missing
- missing==0 means covered
Result: requirement map drives shrink
extras help shrink
s = "abca", t = "ac"- need {a:1,c:1}
- "abc" fills both
- last a is extra, drop b, "ca" still need-satisfied
Result: "ca"
not fixed m
s = "abca", t = "abc"- m would be 3 but you still shrink/expand
- "abc" and "bca" both cover
Result: variable covering, not anagram-slide
Try it
Write minCover(s, t). s is the source string. t is the requirement string. need[ch] is how many of ch t still wants. missing is unfilled units. The window includes s[L..R] and grows or shrinks. Return the shortest cover. BANC length 4. ca length 2. Covering is variable length, not anagram-slide.
s and t are nonempty. s contains at least one covering of t.