让我们从左到右遍历字符串 $s$ 中的所有字符，同时维护两个数组 $\text{pos}_0$ 和 $\text{pos}_1$，其中 $\text{pos}_0$ 存储所有以 '0' 结尾的子序列的编号，$\text{pos}_1$ 存储所有以 '1' 结尾的子序列的编号。

• 如果遇到 '0'，最好的选择是将其附加到某个以 '1' 结尾的现有子序列上。如果不存在这样的子序列，则需要创建一个新的以 '0' 结尾的子序列。否则，我们需要将一个以 '1' 结尾的子序列转换为以 '0' 结尾的子序列。
• 对于字符 '1' 的处理方式相同。

因此，当不需要创建新子序列时，我们尽量不创建。数组 $\text{pos}_0$ 和 $\text{pos}_1$ 中的值帮助我们确定每个字符被分配到的子序列编号。

此外，Gassa 给出了一个巧妙的证明：设 $f(i)$ 表示长度为 $i$ 的前缀中字符 '1' 的数量减去字符 '0' 的数量。我们断言答案就是 $\max(f(i)) - \min(f(i))$，下面解释为什么这是正确的。在平面上构造点 $(i, f(i))$，然后我们可以将 $\min(f(i))$ 和 $\max(f(i))$ 之间的每个整数 $x$ 与某个子序列相匹配。

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		vector<int> ans(n);
		vector<int> pos0, pos1;
		for (int i = 0; i < n; ++i) {
			int newpos = pos0.size() + pos1.size();
			if (s[i] == '0') {
				if (pos1.empty()) {
					pos0.push_back(newpos);
				} else {
					newpos = pos1.back();
					pos1.pop_back();
					pos0.push_back(newpos);
				}
			} else {
				if (pos0.empty()) {
					pos1.push_back(newpos);
				} else {
					newpos = pos0.back();
					pos0.pop_back();
					pos1.push_back(newpos);
				}
			}
			ans[i] = newpos;
		}
		cout << pos0.size() + pos1.size() << endl;
		for (auto it : ans) cout << it + 1 << " ";
		cout << endl;
	}
	
	return 0;
}