Score : 1500 points
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.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.
A
,B
, and C
.Input is given from Standard Input in the following format:
S
Print one longest subsequence that satisfies the conditions. If multiple solutions exist, any of them will be accepted.
ABBCBCAB
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.
ABABABABACACACAC
BABCAC
ABCABACBCBABABACBCBCBCBCBCAB
ACABACABABACBCBCBCBCA
AAA
It is possible that only the empty string satisfies the condition.