Alternation (Editorial)

Idea

We need to insert exactly one $0$ and exactly one $1$ into the string so that any two adjacent characters are different.

Notice that if two adjacent characters are both $0$, we must insert a $1$ between them. Similarly, if two adjacent characters are both $1$, we must insert a $0$ between them.

Key Observation

Let b_0 be the number of adjacent pairs $00$, and let b_1 be the number of adjacent pairs $11$.

Since we can insert only one character of each type, the following conditions are necessary:

However, these conditions alone are not sufficient.

In any alternating binary string, the numbers of zeros and ones differ by at most one.

Since we insert exactly one zero and one one, the difference between their counts does not change.

Therefore, if c_0 and c_1 denote the numbers of zeros and ones in the original string, we must also have

Solution

In fact, these three conditions are also sufficient.

First, insert the opposite character between every pair of equal adjacent characters. Since b_0 \leq 1 and b_1 \leq 1, the allowed insertions are enough.

After these insertions, we obtain a string in which all adjacent characters are different.

If both insertions have already been used, we have obtained the required string.

If one insertion remains, we can add the remaining character to one of the ends of the string. This is always possible because |c_0-c_1| \leq 1.

If both insertions remain, the original string is already alternating. In this case, we can simply append $01$ or $10$ to the appropriate end of the string.

Thus, the answer is YES if and only if all three conditions hold:

To check these conditions, a single pass through the original string is sufficient.

Complexity Analysis

All required values can be calculated in a single pass through the string.

The time complexity is $O(n)$.

The additional space complexity is $O(1)$.

Implementation

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

void solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    int c0 = 0, c1 = 0;
    int b0 = 0, b1 = 0;

    for (char c : s) {
        if (c == '0') c0++;
        else c1++;
    }

    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            if (s[i] == '0') b0++;
            else b1++;
        }
    }

    if (b0 <= 1 && b1 <= 1 && abs(c0 - c1) <= 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

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

    solve();
    return 0;
}