No.1609 String Division Machine
タグ : / 解いたユーザー数 36
作問者 : 👑
SPD_9X2
/ テスター :
👑 
tute7627
penguinman
問題文
文字列分割マシンは、文字列 $T$ を入力すると、 $T$ を以下のアルゴリズムに従って複数の部分列に分割して出力します。
- $T$ の部分列のうち、辞書順で最大のものを選ぶ。これは選ぶ位置も含め一意に定まることが証明できます。
- 選んだ部分列を出力し、 $T$ から削除する。
- $T$ が空文字列であれば終了する。そうでなければ、 $1$ に戻る。
出力された部分列の個数を、文字列 $T$ の文字列分割数と呼ぶことにします。（文字列分割数は、上のアルゴリズムの 2. が実行された回数と等しいです。）
英小文字と"?" からなる文字列 $S$ が与えられます。
$S$ の "?" を全て任意の英小文字に置き換えた文字列のうち、文字列分割数が最小のものを求めてください。(全ての"?"は、独立に任意の英小文字に置き換え可能です。)
ただし、該当する文字列が複数個ある場合は辞書順で最小のものを求めてください。
なお、文字列 $T$ の部分列とは、$T$ から $1$ 文字以上の文字を選び、元の順番で連結した文字列のことを指します。
入力
$S$
- $S$ は英小文字と"?"からなる文字列。
- $S$ の終端は、改行文字の入力で表される。
- $1 \le |S| \le 10^5$
出力
答えを $1$ 行に出力してください。 最後に改行してください。
サンプル
サンプル1
入力
?c?b?d?
出力
ccbbada
$T$ は、ccbbada → ccbba → 空文字列 と変化し、 da と ccbba の $2$ つの部分列に分割されます。
文字列分割数を $2$ 未満にする方法はなく、文字列分割数が $2$ である $S$ から作れる文字列のうち、ccbbadaよりも辞書順で小さいものはないため、ccbbadaを出力します。
サンプル2
入力
????
出力
aaaa
$T$ は、 aaaa → 空文字列 と変化し、 aaaa の $1$ つの部分列に分割されます。
サンプル3
入力
?yzab
出力
yyzab
サンプル4
入力
?yzabc
出力
ayzabc
サンプル5
入力
?yz?xyz?tu?def?abc?
出力
xyzxxyzdtuddefaabca
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。