分数: 400 点
问题陈述
给你一个字符串 S 长度 3N,恰好包含 N 字母 A, N 字母 B,和 N 字母 C.
让我们调用一个字符串 T 由字母组成 A, B,和 C 好,如果满足以下条件:
- 的长度 T 可以被整除 3。我们将其表示为 3K.
- T_1 = T_2 = \ldots = T_K
- T_{K+1} = T_{K+2} = \ldots = T_{2K}
- T_{2K+1} = T_{2K+2} = \ldots = T_{3K}.
- 信件 T_1, T_{K+1} 和 T_{2K+1} 彼此不同。
好的字符串的例子是 ABC, BBAACC,和 AAACCCBBB.
想办法分割 S 进入 最多 6 (不一定是连续的)子序列,以便每个子序列中的字母形成一个好的字符串。
可以证明,在问题的约束下,总是可能的。
约束
- 1 \le N \le 2\cdot 10^5
- 字符串 S 包含 N 字母
A, N 字母B,和 N 字母C.
输入
输入由标准输入按以下格式给出:
N S
输出
输出一个长度的字符串 3N,仅包含来自 1 to 6。 对于每一个 1\le i \le 6 出现在你的字符串中,字符 S 在您输出的位置 i 必须形成良好的字符串。 如果有多种可能的解决方案,则打印其中任何一个都将被认为是正确的。
示例输入 1
2 ABCCBA
示例输出 1
111222
S 被分成子序列 ABC 和 CBA,每个都是一个好字符串。
示例输入 2
4 AABCBCAACBCB
示例输出 2
111211241244
的位置 1 形成一个子序列 AABBCC,位置 2 形成一个子序列 CAB,以及位置 4 形成一个子序列 ACB。
所有这些字符串都很好。