Let \(A_i=(\)the number of 0 in \(S_1,S_2,\ldots,S_i)\) and \(B_i=(\)the number of 1 in \(S_1,S_2,\ldots,S_i)\). (Define \(A_0=B_0=0\).)

Given a pair of integers \((l,r)\) \((1 \leq l \leq r \leq N+1)\), let us consider how many operations are needed so that \(S_i=\) 1 if and only if \(l \leq i < r\).

First, we need to operate as many times as the number of indices \(i\) \((1 \leq i \leq N)\) with \(l \leq i <r\) such that \(S_i=\) 0. This count is represented as \(A_{r-1}-A_{l-1}\). Moreover, we further need to operate as many times as the number of indices \(i\) \((1 \leq i \leq N)\) with \(i<l\) or \(r \leq i\) such that \(S_i=\) 1. This count is represented as \(B_N-(B_{r-1}-B_{l-1})\). Conversely, we also see that \(B_N+A_{r-1}-B_{r-1}-A_{l-1}+B_{l-1}\) operations are sufficient.

Therefore, it is sufficient to find the minimum \(A_{r-1}-B_{r-1}-A_{l-1}+B_{l-1}\) over all possible integer pairs \((l,r)\) \((1 \leq l \leq r \leq N+1)\). If we define \(C_i=A_i-B_i\), the count can be written as \(C_{r-1}-C_{l-1}\). The minimum value of \(C_{r-1}-C_{l-1}\) for a sequence \(C\) can be found as \(\displaystyle \min_{1 \leq l \leq r \leq N+1} C_{r-1}-C_{l-1}=\min_{1 \leq r \leq N+1} (C_{r-1}-\max_{1 \leq l \leq r}C_{l-1})\), which allows us to scan \(C\) for \(r=1,2,\ldots,N+1\) in order while maintaining the tentative maximum value of \(C\) to find the sought minimum value in a total of \(\mathrm{O}(N)\) time.

Hence, the problem itself can also be solved in a total of \(\mathrm{O}(N)\) time.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> c(n + 1);
    for (int i = 0; i < n; ++i) {
        c[i + 1] = c[i] + (s[i] == '0' ? 1 : -1);
    }
    int sum = count(s.begin(), s.end(), '1');
    int ma = 0;
    int res = 0;
    for (int i = 0; i <= n; ++i) {
        res = min(res, c[i] - ma);
        ma = max(ma, c[i]);
    }
    cout << sum + res << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}