分数: 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