C - Permutation of Length 26 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 100

問題文

この問題においては、「1 番目の文字」で文字 a を、「2 番目の文字」で文字 b を、...、「26 番目の文字」で文字 z を指すものとします。

英小文字からなる文字列 S が与えられます。

あなたは 1\leq L\leq R\leq |S| となる整数 L, R および (1,2,\ldots,26) の順列 (p_1,p_2,\ldots,p_{26}) を選びます。その後、以下の手順で新たな文字列 T を作ります。

  1. S'SL 文字目から R 文字目を取り出してできる文字列とする。
  2. 1 以上 26 以下の全ての整数 i について、S' に含まれる「i 番目の文字」を「p_i 番目の文字」で置き換える。この操作は全ての i に対して同時に行う。この結果できる文字列を T とする。

T として考えられる文字列のうち辞書順で最大のものを求めてください。

制約

  • 1\leq |S|\leq 10^5
  • S は英小文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。


入力例 1

abcba

出力例 1

zyzx

L=2,R=5,(p_1,p_2,\ldots,p_{26})=(24,26,25,1,2,3,\ldots,23) とすると、Tzyzx になります。T としてありえるものの中でこれが辞書順で最大です。


入力例 2

nolemonnomelon

出力例 2

zzyxwvyz

入力例 3

hhhhhqqqhhhhhjjhhhhhpppp

出力例 3

zzzzzyyzzzzzxxxx