You are given a binary string s of length n . The...

Idea

When you pick a subsequence and look only at consecutive equal pairs,
every run of identical characters of length ℓ contributes ℓ − 1 to the score.
Hence for a subsequence of total length L that is broken into k runs

score = (ℓ1−1)+(ℓ2−1)+ … + (ℓk−1) = L − k.      (1)

To maximize the score we must minimise the number of runs.
With just two symbols (0 and 1) the best we can do is:

• keep only one kind of symbol ⇒ one run, score L−1;
• or keep a block of some 0’s followed by a block of some 1’s
  ⇒ exactly two runs, score L−2.

Anything with more than one transition (0 → 1 → 0 → …) has k ≥ 3 and is strictly worse than deleting the middle runs.

So the optimal subsequence has at most one transition.

---

How to compute it

For every cut‐point between positions i−1 | i

text
zeros  = number of ‘0’s in s[0 … i−1]      (prefix)
ones   = number of ‘1’s in s[i … n−1]      (suffix)

text
candidate score =
    zeros+ones − 1   if (zeros==0 xor ones==0)   // one run
    zeros+ones − 2   otherwise                   // two runs

Taking the maximum over all cuts also covers the “all-zeros” and “all-ones” cases (cuts before the first and after the last character).

We can evaluate this in O(n) with two prefix/suffix arrays.

---

Correctness proof (sketch)

Lemma 1 Any subsequence with more than one 0→1 transition can be modified (by deleting inner runs) to a subsequence with fewer runs and no smaller score—because deleting one character from every inner run reduces both L and k by 1, leaving L−k unchanged.

Lemma 2 Therefore an optimal subsequence has at most one transition.

Lemma 3 For a fixed cut the construction above gives the best subsequence with at most one transition, because we simply take every possible 0 before the cut and every possible 1 after it.

Combining Lemmas 2 and 3 and maximising over all cuts yields the global optimum, so the algorithm is correct.

---

Complexity

For each test-case
prefix0 and suffix1 are filled in O(n) time and memory.
The single scan over all cuts is also O(n).

Σ n ≤ 10^5, so the whole program easily fits in the limits.

---

Reference implementation (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;                                  // number of test-cases
    cin >> T;
    while (T--) {
        int n;  string s;
        cin >> n >> s;

        vector<int> pref0(n + 1, 0), suf1(n + 1, 0);

        for (int i = 0; i < n; ++i)          // prefix zeros
            pref0[i + 1] = pref0[i] + (s[i] == '0');

        for (int i = n - 1; i >= 0; --i)     // suffix ones
            suf1[i] = suf1[i + 1] + (s[i] == '1');

        int best = 0;
        for (int i = 0; i <= n; ++i) {       // cut between i−1 | i
            int z = pref0[i];
            int o = suf1[i];
            if (z == 0 && o == 0) continue;  // impossible, but safe

            int cand = z + o - ((z == 0 || o == 0) ? 1 : 2);
            best = max(best, cand);
        }
        cout << best << '\n';
    }
    return 0;
}

The program follows exactly the logic proved above and satisfies the required O(n) time and memory bounds.

Here’s the fix: you need to consider both possible one-transition patterns—either all 0’s then all 1’s or all 1’s then all 0’s. The original only did 0→1. Below is a corrected O(n) solution:

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        // prefix counts of 0/1 and suffix counts of 0/1
        vector<int> p0(n+1,0), p1(n+1,0), s0(n+1,0), s1(n+1,0);
        for (int i = 0; i < n; i++) {
            p0[i+1] = p0[i] + (s[i]=='0');
            p1[i+1] = p1[i] + (s[i]=='1');
        }
        for (int i = n-1; i >= 0; i--) {
            s0[i] = s0[i+1] + (s[i]=='0');
            s1[i] = s1[i+1] + (s[i]=='1');
        }

        int best = 0;
        for (int i = 0; i <= n; i++) {
            // pattern 0* then 1*
            int z = p0[i], o = s1[i];
            if (z || o) {
                int cand = z + o - ((z && o) ? 2 : 1);
                best = max(best, cand);
            }
            // pattern 1* then 0*
            int o2 = p1[i], z2 = s0[i];
            if (o2 || z2) {
                int cand2 = o2 + z2 - ((o2 && z2) ? 2 : 1);
                best = max(best, cand2);
            }
        }

        cout << best << "\n";
    }
    return 0;
}

What changed:

• We build both pref0/pref1 and suf0/suf1.
• For each cut i, we compute:
  • 0→1 subsequence score = p0[i] + s1[i] − (p0[i]&&s1[i]?2:1)
  • 1→0 subsequence score = p1[i] + s0[i] − (p1[i]&&s0[i]?2:1)
• Take the maximum over all cuts and both patterns.

This now handles cases like "111000" (beauty = 4) as well as the original examples.