Shortest Full Collection
Medium · sliding window
A collector keeps a shelf of stickers in a row. You are given a list stickers where stickers[i] is the id of the sticker in slot i. Different slots can hold the same id.
The collector wants to take a stretch of the shelf: a run of neighbouring slots, with nothing skipped. The stretch must contain at least one sticker of every distinct id that appears anywhere on the shelf.
Return the number of slots in the shortest such stretch. The whole shelf always qualifies, so there is always an answer.
Examples
Example 1
Input: stickers = [4, 7, 4, 9, 7, 4, 9]
Output: 3
The ids on the shelf are 4, 7 and 9. The stretch [7, 4, 9] in slots 1 to 3 holds all three, and no stretch of two slots can.
Example 2
Input: stickers = [5, 5, 5, 5]
Output: 1
Only one id exists, so a single slot is enough.
Example 3
Input: stickers = [2, 1, 1, 1, 3]
Output: 5
The ids 2 and 3 sit at opposite ends, so the stretch has to cover the whole shelf.
Constraints
- 1 <= len(stickers) <= 5000
- 1 <= stickers[i] <= 10^9