Decide longest versus shortest window
Updated
Longest: expand greedily, shrink only to restore validity, record max length among valid. Shortest: expand until valid, shrink greedily, record min length among valid.
What to focus on
Unique, at-most-k-distinct, at-most-k-zeros, k-replacements, product-under-limit are longest. Covering a requirement and sum-at-least-s are shortest. Mixing the shrink policy gives the wrong extremum.
Worked examples
longest unique
s = "abcabcbb"- keep the longest all-unique
- do not shrink "abc" while it is unique
Result: longest 3
shortest cover
s = "ADOBECODEBANC", t = "ABC"- after cover, shrink
- BANC beats the first longer cover
Result: shortest 4
longest zeros
a = [1, 0, 0, 1, 9], k=1- want max length with zeros ≤ 1
- not the shortest one-zero slice
Result: longest 3
Try it
Write classifyGoal(s). s is a string, or a is an array of integers. Longest expands greedily. Shortest shrinks greedily after the window is valid. Print longest or shortest and which pointer is greedy. Return nothing. For unique "abcabcbb", cover ADOBECODEBANC vs ABC, and zeros k=1 on [1, 0, 0, 1, 9].
s is nonempty and contains a covering of t. a is nonempty. k ≥ 0.