This solution uses queue and deque. The primary concept is that starting from the last '1', we take all the '0's that are before the previous '1'. If the previous digit is '1', then we take the last '0' that is available. If we have no '0's left, we take the first '1' that is available to us. To implement this process, we can store the indices of '0's in a queue and the indices of '1's in a deque. The time complexity is O(n).
Code(C++):
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define dd double
#define ff float
#define ss string
#define ins insert
#define vv vector
//Function to solve problem starts
ll solve(ss s, ll n){
queue<ll> q;
deque<ll> dq;
for(ll i = n — 1; i >= 0; i --){
if(s[i] == '0'){
q.push(i);
}
else{
dq.pb(i);
}
}
ll ans = 0;
for(ll i = n — 1; i >= 0; i --){
if(s[i] == '1'){
if(! dq.empty())
dq.pop_front();
if(! q.empty()){
ans += (i + 1);
q.pop();
while(q.front() > dq.front() && ! q.empty()){
q.pop();
}
}
else{
if(! dq.empty()){
ans += (i + 1);
dq.pop_back();
}
}
}
}
ll total = (n * (n + 1)) / 2;
return total — ans;
}
//Function to solve problem ends
//main function starts
int main(){
ll t;
cin >> t;
while(t --){
ll n;
cin >> n;
ss s;
cin >> s;
cout << solve(s, n) << endl;
}
return 0;
}
//main function ends