/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1600 点
問題文
N 個の a と N 個の b からなる，長さ 2N の文字列 S が与えられます。
あなたは S からいくつかの文字を選びます。ただし各 i = 1,2,...,N について，S で i 番目に出現する a と i 番目に出現する b から片方だけ選ぶことは出来ません。
そして選んだ文字たちを( S での順番通りに)結合します。
こうして得られる文字列のうち，辞書順で最大のものを求めて下さい。
制約
- 1 \leq N \leq 3000
- S は N 個の
aとbからなる，長さ 2N の文字列である。
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
条件を満たす T のうち，辞書順で最大のものを出力して下さい。
入力例 1
3 aababb
出力例 1
abab
S の 1, 3, 4, 6 番目の文字からなる部分列 T は，条件を満たします。
入力例 2
3 bbabaa
出力例 2
bbabaa
全ての文字を選ぶことも可能です。
入力例 3
6 bbbaabbabaaa
出力例 3
bbbabaaa
入力例 4
9 abbbaababaababbaba
出力例 4
bbaababababa
Score : 1600 points
Problem Statement
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
aand N occurrences ofb.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the lexicographically largest string that satisfies the condition.
Sample Input 1
3 aababb
Sample Output 1
abab
A subsequence of T obtained from taking the first, third, fourth and sixth characters in S, satisfies the condition.
Sample Input 2
3 bbabaa
Sample Output 2
bbabaa
You can choose all the characters.
Sample Input 3
6 bbbaabbabaaa
Sample Output 3
bbbabaaa
Sample Input 4
9 abbbaababaababbaba
Sample Output 4
bbaababababa