AtCoder Beginner Contest 242 B問題 Minimize Ordering
問題
提出解答
問題の概要
英小文字からなる文字列 が与えられる.
を並び替えてできる文字列のうち, 辞書式最小の文字列を求めよ.
制約
は英小文字からなる文字列
解法
辞書式順序の最小化より, 先頭から決定していく.
文字目について, 最小化するためには
にある
個の英小文字から最小のものを取ってこなければならない (それを
とする).
文字目について, 最小化するためには,
のうち
以外の
個の英小文字から最小のものを取ってこなければならない (それを
とする).
これを繰り返していくことにより, は
を昇順 *1 に並び替えたものになることに気づく.
よって, をソートしたものを文字列として出力すればよく, 計算量
でできる.
*1: の順