Binary String To Subsequences solution

题意

给定一个01串s，完全分割成若干子序列，其中的子序列不包含两个相邻的0或1(eg:"0101","1010")。对s按这样的分割方式，最少能分出多少串子序列？同时，还要求输出s串中每一字符所在的分割出的子序列编号

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
    int q; 
    scanf("%d", &q);
    while(q--){
        vector<int> ans;
        vector<int> k1, k0;
        int n; 
        scanf("%d", &n);
        string str; 
        cin >> str;
        for (int i = 0; i < n; i++){
            int nk = k0.size() + k1.size();
            if(str[i] == '0'){
                if(k1.empty()){ 
                    k0.push_back(nk);
                } 
                else{ 
                    nk = k1.back(); 
                    k0.push_back(nk); 
                    k1.pop_back(); 
                }
            }
            else {
                if(k0.empty()){ 
                    k1.push_back(nk);
                }
                else{ 
                    nk = k0.back();
                    k1.push_back(nk);
                    k0.pop_back();
                }
            }
            ans.push_back(nk);
        }
        printf("%d
", (int)(k1.size() + k0.size()));
        for (int i = 0; i < n; i++){
            printf("%d%c", ans[i] + 1, (i == n - 1) ? '
' : ' ');
        }
    }
}