The Long Row in the Vintner's Cellar
The vintner of bitwick keeps her barrels in one unbroken row along the cellar wall, each barrel branded with the year of its vintage. A merchant from downriver will buy a single contiguous stretch of that row — barrels taken in order, none skipped — but her cart is fitted with only k racks, and every barrel of one vintage year must ride in a rack of its own. So the stretch she buys may draw on at most k different vintage years. She wants the longest such stretch.
You are given barrels, a list of integers (the vintage year branded on each barrel, in row order, possibly empty), and k, a non-negative integer.
Return a single integer: the greatest number of barrels in a contiguous stretch of barrels that contains at most k distinct values. If no such stretch exists (because barrels is empty, or k is 0), return 0.
examples
- case 1
barrels of [4, 4, 1, 1, 4, 2, 4], k of 25 — the stretch 4, 4, 1, 1, 4 uses only the years 4 and 1; taking the barrel branded 2 as well would need a third rack - case 2
barrels of [7, 7, 7], k of 00 — with no racks she can carry nothing - case 3
barrels of [1, 2, 3, 4, 5], k of 33 — every barrel is a different year, so no stretch longer than 3 fits in 3 racks
- reward
- 320 XP
- signature
longestRow
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- two racks over a mixed row
- no racks at all
- empty cellar
- one vintage, one rack
- all years distinct
- racks to spare
- single barrel
- long row with three racks
- long row with one rack