← 返回题目列表

AtCoder · agc036_e

E. ABC 字符串

中文机器翻译题面 查看原题

分数: 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


可能只有空字符串满足条件。