Shortest Impossible Sequence of Rolls
You are given an integer array rolls of length n and an integer k. You roll a k sided dice numbered from 1 to k, n times, where the result of the i^th roll is rolls[i].
Return the length of the shortest sequence of rolls so that there's no such subsequence in rolls.
A sequence of rolls of length len is the result of rolling a k sided dice len times.
Example 1
Input
rolls = [4,2,1,2,3,3,2,4,1], k = 4Output
3Every sequence of rolls of length 1 and 2 can be taken from
rolls, but the sequence [1, 4, 2] cannot, so the shortest impossible length is 3.Example 2
Input
rolls = [1,1,2,2], k = 2Output
2Every sequence of rolls of length 1 can be taken from
rolls, but the sequence [2, 1] cannot, so the shortest impossible length is 2.Constraints
- n == rolls.length
- 1 <= n <= 10^5
- 1 <= rolls[i] <= k <= 10^5