各 \(x \in \lbrace 0, .. N - 1 \rbrace\) に対して現在の \(x\) の登場回数 count[x] を管理しながら長さ \(M\) の部分文字列（連結な部分列）を左から順に訪問していき、その過程で count[x] == 0 になる時刻が存在するような最小の \(x\) が答えです。部分列を動かす際の count の更新と count[x] == 0 なる \(x\) の発見は必要な箇所だけを見れば定数時間で行えますので、全体で \(\Theta ( N )\) 時間で処理できます。