思路并不困难，重点在于可能的出发点很多，但要快速地找到最适合的那个。

下文用 表示第 个 的出现位置。

看到这种字典序最大的串，第一反应是从前到后按位贪心。但直接枚举结果串的每一位，然后判能否被原串生成是显然不好做的。注意到操作对原串的限制其实不弱，不妨从原串的每一对 入手来考虑问题。

然后发现简单贪心其实不太好做，但你发现问题基本上是分阶段的，可以考虑 DP。

所以设 表示只考虑第 个 与第 个 的最大结果串。

首先 。然后考虑保留第 对 后面怎么决策。如果 在 前面，那么这中间的所有 对应的编号显然都比 小，不能保留；这中间的所有 保留了会更劣，也不能保留。所以此时找到最小的 使得 。 （其中 表示字符串拼接）。

如果 在 前面，情况有所不同。显然夹在中间的所有 都必须保留，那么这些”必须保留的 ”也会给后面一个限制，那么我们找到其中编号最大的 ，设为 。那么接着找到 与 之间编号最大的 ，将 赋值为这个 。一直做下去直到 与 之间全是 。那么编号在 中间的 对都必须保留。我们用 在前面接上 的 对形成的串即可。

时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5;
int n;
char s[N << 1];
int pa[N],pb[N];
int Id[N << 1];
string dp[N];
int main() {
	scanf("%d%s",&n,s + 1);
	for(int i = 1,ca = 0,cb = 0;i <= n + n;i++)
		if(s[i] == 'a') pa[++ca] = i,Id[i] = ca; else pb[++cb] = i,Id[i] = cb;
	for(int i = n;i >= 1;i--) {
		dp[i] = dp[i + 1];
		if(pa[i] < pb[i]) {
			int ps = i + 1;
			while(ps <= n && pa[ps] <= pb[i]) ++ps;
			string v = "ab" + dp[ps];
			if(v > dp[i]) dp[i] = v;
		} else {
			int now = i;
			while(1) {
				int mx = 0;
				for(int i = pb[now] + 1;i < pa[now];i++)
					if(s[i] == 'b') mx = Id[i];
				if(!mx) break;
				now = mx;
			}
			string t = dp[now + 1],t2;
			for(int j = i;j <= pa[now];j++) if(Id[j] >= i) t2 += s[j];
			t = t2 + t;
			if(t > dp[i]) dp[i] = t;
		}
	}
	string ans;
	for(int i = 1;i <= n;i++) if(dp[i] > ans) ans = dp[i];
	cout << ans << endl;
	return 0;
}