SRM563 div1 300

問題

2つの文字列X,Yを考えたとき、前方からどちらかを選んぶことを続けてマージした文字列Sを考える。
ここで、YはXを並び替えたものとすると、Sが与えられたとき、Xとしてありうる文字列の辞書順最小を答える。

考え方

一文字ずつ残りが可能かどうかチェックしながら確定させていく。

Sに含まれる文字の数をアルファベットごとに数を半分にすれば、Xに含まれる文字が得られる。
辞書順最小にするために、先頭から1文字ずつ決めていく。
すでに決めた文字列＋今決めた1文字を、文字列Sの先頭から貪欲に割り当てる。(残りの部分に適当なYを割り当てればよいので)
割り当て終わった次のインデクスから、まだ決めていない残りの文字がすべて割り当て可能かどうかをチェックする。