実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
d
と p
からなる長さ L の文字列 T に対して、T を 180 度回転した文字列を f(T) と表します。より厳密には、f(T) を次の条件を満たす文字列として定めます。
- f(T) は
d
とp
からなる長さ L の文字列である。 - 1 \leq i \leq L であるすべての整数 i について、f(T) の i 文字目は T の L + 1 - i 文字目と異なる。
例えば T = ddddd
のとき f(T) = ppppp
, T = dpdppp
のとき f(T)= dddpdp
です。
d
と p
からなる長さ N の文字列 S が与えられます。
あなたは次の操作を 0 回以上 1 回以下行うことができます。
- 1 \leq L \leq R \leq N である整数の組 (L, R) を 1 つ選び、S の L 文字目から R 文字目までからなる部分文字列を T とする。そして、S の L 文字目から R 文字目までを f(T) に置き換える。
例えば S= dpdpp
, (L,R)=(2,4) の場合、T= pdp
, f(T)= dpd
なので S は ddpdp
に変化します。
最終的な S としてあり得る文字列のうち辞書順最小のものを出力してください。
辞書順とは?
文字列 S = S_1S_2\ldots S_{|S|} が文字列 T = T_1T_2\ldots T_{|T|} より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。
- |S| \lt |T| かつ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}。
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}
- S_i が T_i よりアルファベット順で小さい文字である。
制約
- 1 \leq N \leq 5000
- S は
d
とp
からなる長さ N の文字列 - N は整数
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
6 dpdppd
出力例 1
dddpdd
(L, R) = (2, 5) とします。T = pdpp
, f(T) = ddpd
なので、操作後の S は dddpdd
になります。
得られる文字列のうち dddpdd
が辞書順最小なので、これを出力します。
入力例 2
3 ddd
出力例 2
ddd
操作を行わないことが最適な場合もあります。
入力例 3
11 ddpdpdppddp
出力例 3
ddddpdpdddp
Score : 500 points
Problem Statement
For a string T of length L consisting of d
and p
, let f(T) be T rotated 180 degrees. More formally, let f(T) be the string that satisfies the following conditions.
- f(T) is a string of length L consisting of
d
andp
. - For every integer i such that 1 \leq i \leq L, the i-th character of f(T) differs from the (L + 1 - i)-th character of T.
For instance, if T = ddddd
, f(T) = ppppp
; if T = dpdppp
, f(T)= dddpdp
.
You are given a string S of length N consisting of d
and p
.
You may perform the following operation zero or one time.
- Choose a pair of integers (L, R) such that 1 \leq L \leq R \leq N, and let T be the substring formed by the L-th through R-th characters of S. Then, replace the L-th through R-th characters of S with f(T).
For instance, if S= dpdpp
and (L,R)=(2,4), we have T= pdp
and f(T)= dpd
, so S becomes ddpdp
.
Print the lexicographically smallest string that S can become.
What is lexicographical order?
A string S = S_1S_2\ldots S_{|S|} is said to be lexicographically smaller than a string T = T_1T_2\ldots T_{|T|} if one of the following 1. and 2. holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfies the following two conditions:
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
- S_i is smaller than T_i in alphabetical order.
Constraints
- 1 \leq N \leq 5000
- S is a string of length N consisting of
d
andp
. - N is an integer.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
6 dpdppd
Sample Output 1
dddpdd
Let (L, R) = (2, 5). Then, we have T = pdpp
and f(T) = ddpd
, so S becomes dddpdd
.
This is the lexicographically smallest string that can be obtained, so print it.
Sample Input 2
3 ddd
Sample Output 2
ddd
It may be optimal to skip the operation.
Sample Input 3
11 ddpdpdppddp
Sample Output 3
ddddpdpdddp