1 番目の文字は 1 文字目から \(N - K + 1\) 文字目の中から辞書順で最小の文字を選ぶ. 同じ文字がある場合はそのうち最も左の文字を選ぶのが後の選択肢が増えるので最適である. この文字の位置を \(c_1\) とする.

2 番目の文字は \(c_1 + 1\) 文字目から \(N - K + 2\) 文字目の中から辞書順で最小の文字を選ぶ. 同じ文字がある場合は同様である.

以下これを繰り返して得られた文字が辞書順で最小である.

これを実装するには, 値として \({S_i, i}\) を持つ最小値を返すセグメントツリーを使えばいい.