← 返回题目列表

Codeforces · 1296/E2

E2. 字符串着色(硬版)

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

这是问题的困难版本。实际问题有所不同,但简单版本几乎是困难版本的子任务。请注意,约束和输出格式不同。

给定一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

您必须将其所有字符涂上最少数量的颜色(每个字符只能涂上一种颜色,相同的字母可以涂上相同或不同的颜色,即您可以为 $$$s$$$ 中的每个索引选择恰好一种颜色)。

着色后,您可以交换字符串中任意两个相邻的着色为不同颜色的字符。您可以任意(可能为零)次执行此类操作。

目标是使字符串排序,即所有字符应按字母顺序排列。

您的任务是找到必须为给定字符串着色的最小颜色数,以便在着色后可以按某些交换顺序对它进行排序。请注意,您只需恢复颜色,而不是交换顺序。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$s$$$ 的长度。

输入的第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

输出

在第一行中打印一个整数 $$$res$$$ ($$$1 \le res \le n$$$) — 您必须对给定字符串进行着色的最小颜色数,以便在着色后可以按某种交换顺序对其进行排序。

在第二行中打印任何可能的颜色,这些颜色可用于使用问题陈述中描述的某些交换序列对字符串进行排序。着色是长度为 $$$n$$$ 的数组 $$$c$$$,其中 $$$1 \le c_i \le res$$$ 和 $$$c_i$$$ 表示第 $$$i$$$ 个字符的颜色。

示例

输入 #1

9
abacbecfd

输出 #1

2
1 1 2 1 2 1 2 1 2

输入 #2

8
aaabbcbb

输出 #2

2
1 2 1 2 1 2 1 1

输入 #3

7
abcdedc

输出 #3

3
1 1 1 1 1 2 3

输入#4

5
abcde

输出#4

1
1 1 1 1 1