競プロ典型 90 問 006 - Smallest Subsequence（★5） - けんちょんの競プロ精進記録辞書順最小なものを求めるとき、しばしば貪欲法が有効ですね！ 問題へのリンク editorial 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の長さ の部分文字列であって、辞書順最小のものを求めてください。 制約 辞書順最小 → 貪欲法！ 「辞書順最小のものを求めよ」と言われたら、とにかく貪欲法！！！ まずは求めたい文字列の先頭の文字について、次のように考えます。 もし先頭の文字が a であって、長さ の部分文字列が存在するならば、先頭の文字は a であると考えてよい 文字列 にそもそも文字 a がないとダメ 文字 a があったとしても、その後ろの文字数が 文字未満の場合はダメ そのような部分文字列が存在しないならば、先頭の文字を b にできるかを考える それもダメならば、先頭の文字を c にできるかを考える それもダメならば、先頭の文字を d にできるかを考える ...
