Let us consider the minimum number of operations required to make all digits 0. (Same discussions apply to making all 1.)

First of all, we need to perform at least one operation against each digit that was originally 1. (“Performing an operation against a digit” means removing one digit, flip it, and insert it back.) For each digit that was originally 0, we need to perform an even number of operations, so we either apply zero operations, or two or more operations.

Let us try to maximize the number of digits that was originally 0 for which we do not apply an operation. If we do not perform an operation against digits initially positioned at \(i\)-th and \(j\)-th (\(i < j\)), we cannot perform an operation against any digit between them (\((i+1)\)-th through \((j-1)\)-th). Thus, the digits 0 that we keep untouched must form a single “run” in the original string.

Therefore, if we denote by \(C_0\) the number of 0s in the original string, and by \(M_0\) the maximum length of a run of 0 in the original string, then we need to perform the operation at least twice against each of the \((C_0-M_0)\) 0s, and at least once against each of the \((N-C_1)\) 1s; this means the answer is at least \(2(C_0-M_0)+(N-C_1)\).

Conversely, it is possible to make all digits 0 by \((2(C_0-M_0)+(N-C_1))\) operations. We omit the details here, but for example, we may first turn the string into 0...01...1 form by applying operations against each digit outside the length-\(M_0\) run of 0, and then performing operations against each of the \(C_0-M_0\) 1s (that were originally 0).

Since we can find the values \(C_0\) and \(M_0\) in \(O(N)\) time, the overall time complexity is \(O(N)\).

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

int solve(int n, string s) {
    vector<int> mx(2), cnt(2);
    for (int l = 0; l < n;) {
        int r = l + 1;
        while (r < n and s[l] == s[r]) ++r;
        int c = s[l] - '0';
        int len = r - l;
        mx[c] = max(mx[c], len);
        cnt[c] += len;
        l = r;
    }
    int ans = 2 * n;
    for (int i = 0; i < 2; i++) {
        ans = min(ans, (cnt[i] - mx[i]) * 2 + cnt[i ^ 1]);
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        cout << solve(n, s) << '\n';
    }
}