# 2350. Shortest Impossible Sequence of Rolls
###### tags: `Leetcode` `Hard` `Greedy`
Link: https://leetcode.com/problems/shortest-impossible-sequence-of-rolls/
## 思路 $O(N)$ $O(k)$
思路[参考](https://leetcode.com/problems/shortest-impossible-sequence-of-rolls/)

思考两个问题
1. 什么时候确保所有seq len=1的seq出现过
2. 什么时候确保所有seq len=2的seq出现过

For a sequence of size 1, all k dice must appear in ```rolls```.
For a sequence of size 2, all k dice must appear after all k dice appear in ```rolls```.
... and so on.

So, we go through rolls and count unique dice.

When we have all k dice, we increase the number of sequences ```seq``` and reset the counter.
## Code

class Solution {
    public int shortestSequence(int[] rolls, int k) {
        int cnt = 0;
        int seq = 1;
        int[] dices = new int[k+1];
        for(int roll:rolls){
            if(dices[roll]==seq-1){
                dices[roll]++;
                if(++cnt%k==0) seq++;
            }
        }
        return seq;
    }
}