B - dp Editorial /

Time Limit: 2 sec / Memory Limit: 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 の長さを表します。

  1. |S| \lt |T| かつ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}。
  2. ある整数 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 and p.
  • 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.

  1. |S| \lt |T| and S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. 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 and p.
  • 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