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;
}

What is max OR possible? Take the whole array OR.

Prefix sum of set bits.

First, we find the maximum possible OR of the given array by taking the OR of the whole array in $$$O(n)$$$ time.

Now, we need to find the shortest subarray which will give the OR equal to the max OR found. There are many possible ways to achieve this, some of them are listed below:

1) One possible solution is using two loops to iterate over all subarrays and find the minimum subarray, but the complexity of this approach will be $$$O(n^2)$$$.

2) We can find the minimum subarray in $$$O(32 \cdot n \cdot \log n)$$$ using binary search and prefix sum. First, we store the frequency of set bits in a prefix sum 2D array of size $$$32 \cdot n$$$. Then, we do binary search ($$$\log n$$$) on the answer (from $$$1$$$ to $$$n$$$) to check if it is a possible answer or not. In the predicate function, we can brute force ($$$O(32 \cdot n)$$$) on all possible subarrays of that size. (See solution code for detailed predicate function)

3) We can further reduce the time complexity to $$$O(32 \cdot n)$$$ using the two-pointer method. (See code for this implementation)

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define endl "\n"
#define vl vector<ll>

bool good(vector<vl> &pf,ll m,ll maxx,ll n){
    for(ll i=m;i<=n;i++){
        ll sum = 0;
        for(ll j=0;j<32;j++){
            if((pf[j][i]-pf[j][i-m])>0){
                sum += (1ll<<j);
            }
        }
        if(sum==maxx)
            return true;
    }
    return false;
}

void solve()
{
    ll n;
    cin>>n;
    vl a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    
    ll maxx = 0;
    for(ll i=0;i<n;i++){
       maxx |= a[i];
    }

    vector<bitset<32>> v;
    for(ll i=0;i<n;i++){
        bitset<32> num(a[i]);
        v.pb(num);
    }
 
    vector<vl> pf(32,vl (n+1));
    for(ll i=0;i<32;i++){
        pf[i][0] = 0;
        for(ll j=0;j<n;j++){
            if(v[j][i]){
                pf[i][j+1] = pf[i][j] + 1;
            }
            else{
                pf[i][j+1] = pf[i][j];
            }
        }
    }

    ll l=1,r=n;
    while(r-l>1){
        ll m = l + (r-l)/2;
        if(good(pf,m,maxx,n)){
            r = m;
        }
        else{
            l = m + 1;
        }
    }

    if(good(pf,l,maxx,n)){
        cout<<l<<endl;
    }
    else{
        cout<<r<<endl;
    }
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
        solve();

    return 0;
}

include<bits/stdc++.h>

using namespace std;

define ll long long int

define pb push_back

define endl "\n"

define vl vector

void solve() { ll n; cin>>n; vl a(n); for(ll i=0;i<n;i++){ cin>>a[i]; }

ll maxx = 0;
for(ll i=0;i<n;i++){
   maxx |= a[i];
}

vector<bitset<32>> v;
for(ll i=0;i<n;i++){
    bitset<32> num(a[i]);
    v.pb(num);
}

vector<vl> pf(32,vl (n+1));
for(ll i=0;i<32;i++){
    pf[i][0] = 0;
    for(ll j=0;j<n;j++){
        if(v[j][i]){
            pf[i][j+1] = pf[i][j] + 1;
        }
        else{
            pf[i][j+1] = pf[i][j];
        }
    }
}

ll l=0,r=0;
ll orr = 0;
ll ans = 1e18;
while(l<n && r<n){
    orr |= a[r];
    while(orr==maxx && l<=r){
        ans = min((r-l+1),ans);
        if(l==r)break;
        l++;
        for(ll i=0;i<32;i++){
            if(v[l-1][i])
            if((pf[i][r+1] - pf[i][l]) == 0){
                orr -= (1ll<<i);
            }
        }
    }
    r++;
}
cout<<ans<<endl;

}

int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--) solve();

return 0;

}

Can we think of finding the longest palindrome first and then removing $$$k$$$ characters greedily?

Does the constraints allow us to run a loop of $$$n^2$$$ .

Lets just reverse the problem and length of longest palindromic subsequence that could have been made from original $$$n$$$ letters be L ? now if $$$k$$$ <= $$$n-L$$$ then we can directly say that answer would be as for removing $$$k$$$ letters we will choose them from $$$n-L$$$ pile .

Now what if $$$k>n-L$$$ . How to remove from this subsequence ? We start with removing the middle and answer is always $$$n-k$$$ .

For finding the length of longest palindromic subsequence we can use dynamic programming.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int longestPalindromeSubseq(string s) {
        int n = s.size();
        string b(s.rbegin(), s.rend());
        int dp[n+1][n+1];
        memset(dp,0,sizeof(dp));
        for(int i =1; i<=n;++i){
            for(int j =1; j<=n;++j){
                if(s[i-1]==b[j-1]){
                    dp[i][j]=1+dp[i-1][j-1];
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][n];
}
signed main() {
   int t ; cin >> t;
   while(t--){
     int n;
    cin >> n;
    int k;
    cin >> k;
    
    string s;
    cin >> s;
 
 
   
    int lpsLength = longestPalindromeSubseq(s);
    
 
    
   
    int remainingDeletions = k - (n - lpsLength);
    if(k<=n-lpsLength){
       cout << lpsLength << '\n';
    }
    else{
       int rem = lpsLength -(k - (n - lpsLength));
       cout << rem << '\n';
        
        
 
    }
   }
    return 0;
}

The original question was to also print the subsequence but latter it was discarded to maintain level of contest . Can you do so :).