201481: [AtCoder]ARC148 B - dp

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

给出一个长度为 $N (1 \le N \le 5000)$ 的字符串 $S$，且 $\forall S_i , S_i \in \{d,p \}$。 定义 $rotate (l,r)$，对于区间 $[l,r]$ 的每一个 $i$，重新赋值 $S_i$，使得 $S_i \not= S_{r+l-i}$ （即对称）。 需要执行 $0$ 或 $1$ 次 $rotate (l,r)$（$l,r$ 是任意的），使得 $S$ 字典序最小。

Source/Category

加入题单

上一题 下一题 算法标签：