Synchronized Subsequence

AtCoder

IDagc026_e

Time2000ms

Memory256MB

Difficulty—

You are given a string $S$ of length $2N$, containing $N$ occurrences of `a` and $N$ occurrences of `b`. You will choose some of the characters in $S$. Here, for each $i = 1,2,...,N$, it is not allowed to choose exactly one of the following two: the $i$\-th occurrence of `a` and the $i$\-th occurrence of `b`. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order). Find the lexicographically largest string that can be obtained in this way. ## Constraints * $1 \leq N \leq 3000$ * $S$ is a string of length $2N$ containing $N$ occurrences of `a` and $N$ occurrences of `b`. ## Input Input is given from Standard Input in the following format: $N$ $S$ [samples]

Samples

Input #1

3
aababb

Output #1

abab

A subsequence of $T$ obtained from taking the first, third, fourth and sixth characters in $S$, satisfies the condition.

Input #2

3
bbabaa

Output #2

bbabaa

You can choose all the characters.

Input #3

6
bbbaabbabaaa

Output #3

bbbabaaa

Input #4

9
abbbaababaababbaba

Output #4

bbaababababa

API Response (JSON)

{
  "problem": {
    "name": "Synchronized Subsequence",
    "description": {
      "content": "You are given a string $S$ of length $2N$, containing $N$ occurrences of `a` and $N$ occurrences of `b`. You will choose some of the characters in $S$. Here, for each $i = 1,2,...,N$, it is not allowe",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc026_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S$ of length $2N$, containing $N$ occurrences of `a` and $N$ occurrences of `b`.\nYou will choose some of the characters in $S$. Here, for each $i = 1,2,...,N$, it is not allowe...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments