← 返回题目列表

AtCoder · agc026_e

E. 同步子序列

中文机器翻译题面 查看原题

分数: 1600 点

问题陈述

给你一个字符串 S 长度 2N,包含 N 出现 a 和 N 出现 b.

您将选择其中的一些字符 S。在这里,对于每一个 i = 1,2,...,N,不允许恰好选择以下两项之一: i第 次出现 a 和 i第 次出现 b。 (也就是说,您只能选择两者或都不选择。)然后,您将连接所选的字符(不更改顺序)。

找出按这种方式可以获得的字典序最大的字符串。

约束

  • 1 \leq N \leq 3000
  • S 是一个长度为 2N 包含 N 出现 a 和 N 出现 b.

输入

输入由标准输入按以下格式给出:

N
S

输出

打印满足条件的字典顺序最大的字符串。


示例输入 1

3
aababb

示例输出 1

abab

的子序列 T 通过取第一个、第三个、第四个和第六个字符获得 S,满足条件。


示例输入 2

3
bbabaa

示例输出 2

bbabaa

您可以选择所有字符。


示例输入 3

6
bbbaabbabaaa

示例输出 3

bbbabaaa

示例输入 4

9
abbbaababaababbaba

示例输出 4

bbaababababa