CF1102D Balanced Ternary String

给定一个长度为 $n$ 的字符串 $s$，其中每个字符都是 '0'、'1' 或 '2'。这样的字符串被称为三进制字符串。 你的任务是通过最少的字符替换，将该字符串变为一个平衡三进制字符串（平衡三进制字符串指的是其中 '0'、'1' 和 '2' 的数量都相等）。 在所有可能的平衡三进制字符串中，你需要得到字典序最小的那个。 注意，你不能从字符串中删除字符，也不能添加字符。你只能将给定的字符替换为 '0'、'1' 或 '2'。 保证一定存在答案。

输入的第一行包含一个整数 $n$（$3 \le n \le 3 \cdot 10^5$，$n$ 能被 $3$ 整除），表示字符串 $s$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，其中每个字符都是 '0'、'1' 或 '2'。

输出一个字符串，即通过最少的替换操作，从给定字符串得到的字典序最小的平衡三进制字符串。 由于 $n$ 能被 $3$ 整除，显然一定存在答案，并且答案唯一。

由 ChatGPT 4.1 翻译