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 ith roll is rolls[i].

Return the length of the shortest sequence of rolls that cannot be taken from rolls.

A sequence of rolls of length len is the result of rolling a k sided dice len times.

Note that the sequence taken does not have to be consecutive as long as it is in order.

&nbsp;
Example 1:

Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4
Output: 3
Explanation: Every sequence of rolls of length 1, [1], [2], [3], [4], can be taken from rolls.
Every sequence of rolls of length 2, [1, 1], [1, 2], ..., [4, 4], can be taken from rolls.
The sequence [1, 4, 2] cannot be taken from rolls, so we return 3.
Note that there are other sequences that cannot be taken from rolls.

Example 2:

Input: rolls = [1,1,2,2], k = 2
Output: 2
Explanation: Every sequence of rolls of length 1, [1], [2], can be taken from rolls.
The sequence [2, 1] cannot be taken from rolls, so we return 2.
Note that there are other sequences that cannot be taken from rolls but [2, 1] is the shortest.


Example 3:

Input: rolls = [1,1,3,2,2,2,3,3], k = 4
Output: 1
Explanation: The sequence [4] cannot be taken from rolls, so we return 1.
Note that there are other sequences that cannot be taken from rolls but [4] is the shortest.


&nbsp;
Constraints:


	n == rolls.length
	1 &lt;= n &lt;= 105
	1 &lt;= rolls[i] &lt;= k &lt;= 105


class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        ans = 1
        data = set()

        for roll in rolls:
            data.add(roll)

            if len(data) == k:
                ans += 1
                data.clear()

        return ans
class Solution {
    public int shortestSequence(int[] rolls, int k) {
        int len = 0;
        Set<Integer> set = new HashSet<>();
        for(int i:rolls)
        {
            set.add(i);
            if(set.size()==k)
            {
                set = new HashSet<>();
                len++;
            }
        }
        return len+1;
    }
}
class Solution {
public:
    int shortestSequence(vector<int>& rolls, int k) {
        int len = 1;
        set<int> data ;
        
        for (int i = 0; i < rolls.size(); i++) {
            data.insert(rolls[i]);
            
            if (data.size() == k) {
                len++;
                data = set<int>();
            }
        }
        
        return len;
    }
};
var shortestSequence = function(rolls, k)
{
    let ans=1;
    let sett=new Set();

    for(let i of rolls)
        {
            sett.add(i);
            if(sett.size===k)
                {
                    ans++;
                    sett=new Set();
                }
        }
    return ans;
};
Shortest Impossible Sequence of Rolls