分数: 1500 点
问题陈述
给定的是一个字符串 S 组成 A,B,和 C.
考虑(不一定是连续的)子序列 x of S 满足以下所有条件:
A,B,和C都出现相同的次数 x.- 中没有两个相邻字符 x 是相同的。
在这些子序列中,找到最长的一个。这里有一个子序列 S 是删除零个或多个字符得到的字符串 S.
约束
- 1 \leq |S| \leq 10^6
- S 包括
A,B,和C.
输入
输入由标准输入按以下格式给出:
S
输出
打印一个满足条件的最长子序列。 如果存在多个解决方案,则其中任何一个都将被接受。
示例输入 1
ABBCBCAB
示例输出 1
ACBCAB
考虑子序列 ACBCAB of S。它满足条件,并且是具有这些属性的最长的之一,同时 ABCBCA。
另一方面,子序列 ABCBCAB 和 ABBCCA 不满足条件。
示例输入 2
ABABABABACACACAC
示例输出 2
BABCAC
示例输入 3
ABCABACBCBABABACBCBCBCBCBCAB
示例输出 3
ACABACABABACBCBCBCBCA
示例输入 4
AAA
示例输出 4
可能只有空字符串满足条件。