CF1399D.Binary String To Subsequences

You are given a binary string $s$ consisting of $n$ zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer $t$ independent test cases.

给你一个由 $n$ 个 0 和 1 组成的二进制字符串 $s$。

你的任务是将给定字符串划分为最少数量的子序列，使得字符串中的每个字符恰好属于一个子序列，且每个子序列形如 "010101..." 或 "101010..."（即：子序列中不能包含两个相邻的 0 或两个相邻的 1）。

回顾一下，子序列是指从原序列中删除零个或多个元素（不改变剩余元素的相对顺序）所得到的序列。例如，"1011101" 的子序列包括 "0"、"1"、"11111"、"0111"、"101"、"1001"，但不包括 "000"、"101010" 和 "11100"。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $s$. The second line of the test case contains $n$ characters '0' and '1' — the string $s$.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).

输入的第一行包含一个整数 $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$）。

For each test case, print the answer: in the first line print one integer $k$ ($1 \le k \le n$) — the minimum number of subsequences you can divide the string $s$ to. In the second line print $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the number of subsequence the $i$-th character of $s$ belongs to.

If there are several answers, you can print any.

对于每个测试用例，输出答案：第一行输出一个整数 $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$ 个字符所属的子序列编号。

若存在多个合法答案，输出任意一个即可。