CF1296E2 String Coloring (hard version)

这是该问题的困难版本。实际问题有所不同，但简单版本几乎是困难版本的一个子任务。请注意约束条件和输出格式也不同。 给定一个由 $n$ 个小写拉丁字母组成的字符串 $s$。 你需要用最少的颜色对字符串中的所有字符进行染色（每个字符恰好染一种颜色，相同的字母可以染相同或不同的颜色，即你可以为 $s$ 中的每个下标选择恰好一种颜色）。 染色后，你可以交换任意两个相邻且颜色不同的字符。你可以进行任意次数（也可以为零次）这样的操作。 目标是使字符串变为有序，即所有字符按字母顺序排列。 你的任务是求出最少需要多少种颜色对给定字符串染色，使得经过某些交换操作后可以将其变为有序。注意，你只需要输出一种可行的染色方案，而不需要输出交换操作的具体序列。

输入的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

第一行输出一个整数 $res$（$1 \le res \le n$），表示将字符串染色后能够通过交换操作变为有序所需的最少颜色数。 第二行输出任意一种可行的染色方案，用一个长度为 $n$ 的数组 $c$ 表示，其中 $1 \le c_i \le res$，$c_i$ 表示第 $i$ 个字符的颜色。

由 ChatGPT 4.1 翻译