Answer is $$$-1$$$ only when $$$s[0] = 0$$$ (first character in string is 0), think about it.

Look at the positions of $$$1$$$ in the string and the corresponding position in the permutation. This part of the permutation is always sorted in ascending order.

If $$$s[0] = 0$$$, then no solution exists as first element of p is always maximum of $$$[p_1]$$$.

Else, A valid permutation is:

We iterate over the string in reverse. The last occurrence of $$$1$$$ has the maximum value in the entire array, the second last occurrence has the second highest value… We fill p accordingly.

With those values from $$$1$$$ to $$$n$$$ which are still left with us, we iterate in reverse over all the zeros then, using the same process. This creates a valid permutation always in $$$O(n)$$$ time.

#include<bits/stdc++.h>
using namespace std;
string s;
vector<int> v;
 int main() {
     ios_base::sync_with_stdio(false); 
     cin.tie(NULL);
     cout.tie(NULL);
     int t;
     cin>>t;
     while(t--){
     int n;
     cin>>n;
     cin>>s;
     v.resize(n);
     int c = n;
     if(s[0]=='0')
     cout<<-1<<endl;
     else{
     for(int i=n-1;i>=0;i--){
        if(s[i]=='1'){
            v[i] = c;
            c--;
        }}
     for(int i=n-1;i>=0;i--){
        if(s[i]=='0'){
            v[i] = c;
            c--;
        }}
     for(int i=0;i<n;i++)
     cout<<v[i]<<" ";
     cout<<endl;
        v.clear();
     }}
     return 0;
}