dp

AtCoder

IDarc148_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

6
dpdppd

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.

Input #2

3
ddd

Output #2

ddd

It may be optimal to skip the operation.

Input #3

11
ddpdpdppddp

Output #3

ddddpdpdddp

API Response (JSON)

{
  "problem": {
    "name": "dp",
    "description": {
      "content": "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 str",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc148_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\n*   $f(T)$ is a str...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments