Cow Lineup

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of N breed IDs, remove at most K distinct breed IDs so that the longest run of equal IDs in the remaining sequence is maximized.

Level: Medium6 of 10
Topics: Sliding window, Two pointers, Hash map, Array
Solved: No attempts yet

Problem

Farmer John's $N$ cows ( $1 \le N \le 100{,}000$ ) are lined up in a row. Each cow has an integer breed ID in the range $0 \le B(i) \le 1{,}000{,}000{,}000$ ; the breed ID of the $i$ -th cow in the lineup is $B(i)$ . Multiple cows may share the same breed ID.

FJ thinks his lineup looks far more impressive when a long, contiguous block of cows all share the same breed ID. To create such a block, FJ may choose at most $K$ breed IDs and remove from the lineup every cow whose breed ID is one of the chosen IDs; the remaining cows keep their order and close up the gaps. Determine the maximum possible length of a contiguous block of cows that all share the same breed ID after this removal.

Input

Line 1: Two space-separated integers, $N$ and $K$ .
Lines 2 to $N+1$ : Line $i+1$ contains the breed ID $B(i)$ .

Output

Line 1: The maximum size of a contiguous block of cows sharing the same breed ID that FJ can create.

Hint

There are 9 cows with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7, and FJ may remove at most 1 breed ID.

Removing every cow with breed ID 3 turns the lineup into 2, 7, 7, 7, 7, 5, 7, which contains a contiguous block of 4 cows all sharing breed ID 7.

Examples1

Example 1
Input
```
9 1
2
7
3
7
7
3
7
5
7
```
Expected output
```
4
```