题目描述

给定一个由 A、B、C 组成、长度为 $N$ 的字符串 $S$。

你可以对 $S$ 进行如下两种操作，操作的顺序和次数不限：

• 从 $S$ 中选择一个 A 并删除，在该位置写入新的 BB。
• 从 $S$ 中选择一对相邻的 BB 并删除，在该位置写入新的 A。

请你求出所有可能通过上述操作得到的 $S$ 中，字典序最小的字符串。

什么是字典序？字典序简单来说就是“单词在字典中的排列顺序”。更严格地说，判断两个不同字符串 $S$ 和 $T$ 的大小的算法如下：

设 $S$ 的第 $i$ 个字符记为 $S_i$。若 $S$ 字典序小于 $T$，记作 $S < T$；若大于，记作 $S > T$。

1. 取 $S$ 和 $T$ 中较短的字符串长度为 $L$，依次比较 $i=1,2,\dots,L$ 的 $S_i$ 和 $T_i$ 是否相同。
2. 若存在 $S_i \neq T_i$ 的 $i$，取最小的此类 $i$ 为 $j$，比较 $S_j$ 和 $T_j$，若 $S_j$ 的字母顺序小于 $T_j$，则 $S < T$，否则 $S > T$，算法结束。
3. 若所有 $S_i = T_i$，则比较长度，若 $S$ 比 $T$ 短，则 $S < T$，否则 $S > T$，算法结束。

输入格式

输入从标准输入读入，格式如下：

$N$ $S$

输出格式

请输出答案。

样例 1

输入

4
CBAA

输出

CAAB

样例 2

输入

1
A

输出

A

样例 3

输入

6
BBBCBB

输出

ABCA

说明/提示

限制条件

• $1 \leq N \leq 200000$
• $S$ 是由 A、B、C 组成的长度为 $N$ 的字符串

样例解释 1

可以按如下方式操作：

• 初始时，$S=$CBAA。
• 删除第 3 个字符的 A，写入 BB，$S=$CBBBA。
• 删除第 2、3 个字符的 BB，写入 A，$S=$CABA。
• 删除第 4 个字符的 A，写入 BB，$S=$CABBB。
• 删除第 3、4 个字符的 BB，写入 A，$S=$CAAB。

无法将 $S$ 变为比 CAAB 字典序更小的字符串。因此答案为 CAAB。

样例解释 2

一次操作都不进行。

由 ChatGPT 4.1 翻译