E - ABC String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1500 点

問題文

A,B,C からなる文字列 S が与えられます。

S の連続とは限らない部分列 x であって、次の条件をすべて満たすもののうち、最長のものを 1 つ求めてください。 なお、S の部分列とは、S から 0 個以上の文字を削除して得られる文字列を意味します。

  • x に含まれる A,B,C それぞれの個数は全て等しい。
  • x の中で同じ文字は隣り合わない。

制約

  • 1 \leq |S| \leq 10^6
  • S は A,B,C からなる。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

条件を満たす最長の部分列を 1 つ出力せよ。 解が複数ある場合は、どれを出力しても正解とみなされる。

入力例 1

ABBCBCAB

出力例 1

ACBCAB

S の部分列として、ACBCAB を考えると、これは条件を満たしており、またこれが最長です。 また、ABCBCA も条件を満たす最長の部分列です。 ABCBCAB, ABBCCA なども S の部分列ですが、これらは条件を満たしません。

入力例 2

ABABABABACACACAC

出力例 2

BABCAC

入力例 3

ABCABACBCBABABACBCBCBCBCBCAB

出力例 3

ACABACABABACBCBCBCBCA

入力例 4

AAA

出力例 4




条件を満たす部分列が空文字列のみのこともあります。






Score : 1500 points







Problem Statement
Given is a string S consisting of A,B, and C.


Consider the (not necessarily contiguous) subsequences x of S that satisfy all of the following conditions:


    

  • A, B, and C all occur the same number of times in x.
    • 

  • No two adjacent characters in x are the same.
    • 



Among these subsequences, find one of the longest. Here a subsequence of S is a string obtained by deleting zero or more characters from S.











Constraints
    

  • 1 \leq |S| \leq 10^6
    • 

  • S consists of A,B, and C.
    • 
















Input
Input is given from Standard Input in the following format:


S













Output
Print one longest subsequence that satisfies the conditions.
If multiple solutions exist, any of them will be accepted.















Sample Input 1
ABBCBCAB













Sample Output 1
ACBCAB




Consider the subsequence ACBCAB of S. It satisfies the conditions and is one of the longest with these properties, along with ABCBCA.
On the other hand, the subsequences ABCBCAB and ABBCCA do not satisfy the conditions.













Sample Input 2
ABABABABACACACAC













Sample Output 2
BABCAC















Sample Input 3
ABCABACBCBABABACBCBCBCBCBCAB













Sample Output 3
ACABACABABACBCBCBCBCA















Sample Input 4
AAA













Sample Output 4



It is possible that only the empty string satisfies the condition.