← 返回题目列表

Codeforces · 1102/D

D. 平衡三元字符串

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

给定一个字符串 $$$s$$$,由 $$$n$$$ 个字符组成,每个字符要么是“0”、“1”或“2”。这样的字符串称为三元字符串。

你的任务是用其他字符替换该字符串中的最小字符数,以获得平衡三元字符串(平衡三元字符串是一个三元字符串,使得该字符串中字符“0”的数量等于字符“1”的数量,并且字符“1”(显然还有“0”)的数量等于字符“2”的数量)。

在所有可能的平衡三元字符串中,您必须获得按字典顺序(按字母顺序)最小的字符串。

请注意,您既不能从字符串中删除字符,也不能向字符串中添加字符。另请注意,您只能将给定字符替换为字符“0”、“1”和“2”。

保证答案存在。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$n$$$ 可被 $$$3$$$ 整除) — $$$s$$$ 中的字符数。

第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符“0”、“1”和“2”组成。

输出

打印一个字符串 — 按字典顺序(按字母顺序)排列的最小平衡三元字符串,可以通过最少的替换次数从给定的字符串中获得。

因为 $$$n$$$ 可以被 $$$3$$$ 整除,所以显然答案存在。很明显,只有一个可能的答案。

示例

输入 #1

3
121

输出 #1

021

输入 #2

6
000000

输出 #2

001122

输入 #3

6
211200

输出 #3

211200

输入#4

6
120110

输出#4

120120