Чергування (Розбір)

Ідея

Нам потрібно вставити в рядок рівно один символ $0$ та один символ $1$ так, щоб усі сусідні символи були різними.

Зауважимо, що якщо в початковому рядку є два сусідні нулі, між ними обов'язково потрібно вставити одиницю. Аналогічно, між двома сусідніми одиницями потрібно вставити нуль.

Ключове спостереження

Позначимо через b_0 кількість сусідніх пар $00$, а через b_1 — кількість сусідніх пар $11$.

Оскільки ми можемо вставити лише по одному символу кожного виду, необхідно, щоб

Проте цього недостатньо.

У будь-якому знакозмінному двійковому рядку кількості нулів та одиниць відрізняються не більше ніж на один.

Оскільки ми додаємо рівно один нуль та одну одиницю, різниця між їхніми кількостями не змінюється.

Отже, якщо c_0 та c_1 — кількості нулів та одиниць у початковому рядку, то також повинна виконуватися умова

Розв'язок

Насправді цих трьох умов достатньо.

Спочатку вставимо протилежні символи між усіма парами однакових сусідніх символів. Оскільки b_0 \leq 1 та b_1 \leq 1, нам вистачить дозволених вставок.

Після цього отримаємо рядок, у якому всі сусідні символи різні.

Якщо обидві вставки вже використані, потрібний рядок отримано.

Якщо залишилася одна вставка, відповідний символ можна додати на один із кінців рядка. Це можливо завдяки умові |c_0-c_1| \leq 1.

Якщо ж залишилися обидві вставки, початковий рядок уже був знакозмінним. Тоді можна додати $01$ або $10$ на відповідний кінець рядка.

Таким чином, відповідь YES тоді й лише тоді, коли одночасно виконуються три умови:

Для перевірки достатньо одного проходу по початковому рядку.

Асимптотика

Усі необхідні величини можна порахувати за один прохід по рядку.

Часова складність — $O(n)$.

Додаткова пам'ять — $O(1)$.

Реалізація

#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;
}