#166MediumSliding Window· Variable Window with Frequency Map

Longest Run With K Flavors

A juice stand lines up fruit crates on a conveyor belt, each crate labelled with an integer flavour code. A tasting box can be filled by grabbing a **contiguous** stretch of crates from the belt, and the box has room for at most `k` different flavours (any number of crates of the same flavour fit). Given the belt `crates` and the integer `k`, return the length of the longest contiguous stretch that contains at most `k` distinct flavours.

Input format

`crates`: an array of integers (flavour codes); `k`: a positive integer.

Output format

An integer: the length of the longest contiguous subarray with at most `k` distinct values.

Examples

Input: crates = [1, 2, 1, 2, 3], k = 2

Output: 4

The stretch [1, 2, 1, 2] holds two flavours and has length 4. Adding the 3 would make three flavours.

Input: crates = [4, 4, 4], k = 1

Output: 3

All three crates share one flavour, so the whole belt fits.

Input: crates = [7, 8, 9, 10], k = 1

Output: 1

Every crate is a different flavour, so with k = 1 the best stretch is a single crate.

Constraints

1 <= crates.length <= 10^5
0 <= crates[i] <= 10^9
1 <= k <= 10^5

#sliding-window
#hash-table
#two-pointers