题目描述

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

请你求出 $S$ 的一个不一定连续的子序列 $x$，使得 $x$ 满足以下所有条件，并且在所有满足条件的子序列中长度最长。子序列指的是从 $S$ 中删除 $0$ 个或多个字符后得到的字符串。

• $x$ 中包含的 A、B、C 的数量都相等。
• 在 $x$ 中，相同的字符不会相邻出现。

输入格式

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

$S$

输出格式

请输出满足条件的最长子序列中的一个。如果有多个答案，输出其中任意一个都视为正确。

样例 1

输入

ABBCBCAB

输出

ACBCAB

样例 2

输入

ABABABABACACACAC

输出

BABCAC

样例 3

输入

ABCABACBCBABABACBCBCBCBCBCAB

输出

ACABACABABACBCBCBCBCA

样例 4

输入

AAA

输出

说明/提示

限制

• $1 \leq |S| \leq 10^6$
• $S$ 仅由 A、B、C 组成。

样例解释 1

以 $S$ 的子序列 ACBCAB 为例，它满足所有条件，并且是最长的。ABCBCA 也是满足条件的最长子序列。ABCBCAB、ABBCCA 等虽然是 $S$ 的子序列，但不满足条件。

样例解释 4

有时，唯一满足条件的子序列可能是空字符串。

由 ChatGPT 4.1 翻译