Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 242 B問題 Minimize Ordering

AtCoder ABC ABC242 B問題 200 pts

問題

提出解答

問題の概要

英小文字からなる文字列 $S$ が与えられる. $S$ を並び替えてできる文字列のうち, 辞書式最小の文字列を求めよ.

制約

$S$ は英小文字からなる文字列
$1 \leq |S| 2 \times 10^5$

解法

辞書式順序の最小化より, 先頭から決定していく.

$1$ 文字目について, 最小化するためには $S$ にある $|S|$ 個の英小文字から最小のものを取ってこなければならない (それを $T_1$ とする).
$2$ 文字目について, 最小化するためには, $S$ のうち $T_1$ 以外の $|S|-1$ 個の英小文字から最小のものを取ってこなければならない (それを $T_2$ とする).
$\vdots$

これを繰り返していくことにより, $T$ は $S$ を昇順 *1 に並び替えたものになることに気づく.

よって, $S$ をソートしたものを文字列として出力すればよく, 計算量 $O(|S| \ log |S|)$ でできる.

*1: $a,b, \dots, z$ の順