CF1399D Binary String To Subsequences

给定一个由 $n$ 个 $0$ 和 $1$ 组成的二进制字符串 $s$。 你的任务是将该字符串划分为最少数量的子序列，使得字符串中的每个字符恰好属于一个子序列，并且每个子序列的形式都是“010101...”或“101010...”（即子序列中不能有两个相邻的 $0$ 或 $1$）。 回忆一下，子序列是可以通过删除原序列中的零个或多个元素（不改变剩余元素的顺序）得到的序列。例如，"1011101" 的子序列有 "0"、"1"、"11111"、"0111"、"101"、"1001"，但没有 "000"、"101010" 和 "11100"。 你需要回答 $t$ 个独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来有 $t$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。第二行包含 $n$ 个字符 '0' 和 '1'，表示字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每个测试用例，输出两行答案：第一行输出一个整数 $k$（$1 \le k \le n$），表示将字符串 $s$ 划分为的最少子序列数。第二行输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le k$），其中 $a_i$ 表示字符串 $s$ 的第 $i$ 个字符属于第 $a_i$ 个子序列。 如果有多种答案，输出任意一种均可。

由 ChatGPT 4.1 翻译