Colorful String (Editorial)

Розглянемо, що означає умова «рядки відрізняються в кожній позиції».

Обидва отримані рядки мають довжину $n$. Якщо вони відрізняються в кожній позиції $p$, то символи \text{чорний}_p та \text{червоний}_p утворюють пару, у якій один нуль, а інший одиниця — інших варіантів для двійкових символів немає.

Таких пар рівно $n$, і разом вони охоплюють усі $2n$ символів рядка. Отже, у всьому рядку має бути рівно $n$ одиниць і рівно $n$ нулів.

Ця умова не лише необхідна, а й достатня. Якщо одиниць рівно $n$ (а отже, і нулів рівно $n$), поставимо у відповідність кожній одиниці якийсь нуль — утвориться $n$ пар. Тепер із кожної пари пофарбуємо один символ у червоний, а другий залишимо чорним, узгодивши порядок так, щоб партнери потрапили на однакові позиції у своїх рядках. Отримані рядки відрізнятимуться скрізь.

Отже, весь розв'язок — порахувати кількість одиниць і порівняти її з $n$: якщо збігається, виводимо Yes, інакше No. Складність — $\mathcal{O}(n)$.