2350. Shortest Impossible Sequence of Rolls Hard

1/**
2 * [2350] Shortest Impossible Sequence of Rolls
3 *
4 * 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].
5 * Return the length of the shortest sequence of rolls that cannot be taken from rolls.
6 * A sequence of rolls of length len is the result of rolling a k sided dice len times.
7 * Note that the sequence taken does not have to be consecutive as long as it is in order.
8 *  
9 * Example 1:
10 * 
11 * Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4
12 * Output: 3
13 * Explanation: Every sequence of rolls of length 1, [1], [2], [3], [4], can be taken from rolls.
14 * Every sequence of rolls of length 2, [1, 1], [1, 2], ..., [4, 4], can be taken from rolls.
15 * The sequence [1, 4, 2] cannot be taken from rolls, so we return 3.
16 * Note that there are other sequences that cannot be taken from rolls.
17 * Example 2:
18 * 
19 * Input: rolls = [1,1,2,2], k = 2
20 * Output: 2
21 * Explanation: Every sequence of rolls of length 1, [1], [2], can be taken from rolls.
22 * The sequence [2, 1] cannot be taken from rolls, so we return 2.
23 * Note that there are other sequences that cannot be taken from rolls but [2, 1] is the shortest.
24 * 
25 * Example 3:
26 * 
27 * Input: rolls = [1,1,3,2,2,2,3,3], k = 4
28 * Output: 1
29 * Explanation: The sequence [4] cannot be taken from rolls, so we return 1.
30 * Note that there are other sequences that cannot be taken from rolls but [4] is the shortest.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	n == rolls.length
36 * 	1 <= n <= 10^5
37 * 	1 <= rolls[i] <= k <= 10^5
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/shortest-impossible-sequence-of-rolls/
43// discuss: https://leetcode.com/problems/shortest-impossible-sequence-of-rolls/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn shortest_sequence(rolls: Vec<i32>, k: i32) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2350() {
61    }
62}
63