Унікальні літери#525

Унікальні літери (Розбір)

Спершу з'ясуємо, що робить унікалізація з відсортованим рядком.

Нехай усі однакові літери йдуть підряд. Перша a додається в , друга — виштовхує першу (стек повертається до попереднього стану), третя знову додається, і так далі. Отже, після обробки блоку з однакових літер ця літера залишається в тоді й лише тоді, коли непарне, а решта стека не змінюється.

Звідси головне спостереження:

\text{унікалізація відсортованого } s \;=\; \text{відсортований список літер, що трапляються в } s \text{ непарну кількість разів}.

Необхідні умови. Рядок завжди складається з різних літер, тому в не може бути повторів. Крім того, кожна літера мусить траплятися в . Якщо щось із цього порушено — відповідь NO.

Простий випадок. Якщо для кожної літери сума \mathrm{cnt}_s + \mathrm{cnt}_t парна (тобто літера входить у непарну кількість разів рівно тоді, коли вона є в ), достатньо вивести відсортовані і — за спостереженням вище результат збігається з .

Загальний випадок. Назвемо літеру проблемною, якщо \mathrm{cnt}_s + \mathrm{cnt}_t для неї непарна. Проблемним літерам треба «зіпсувати» парність, не змінивши решту. Це робить така обгортка: виведемо літеру , потім по одному разу кожну проблемну літеру, а потім знову . Друга поява виштовхує все, що додалося після першої, тож стек повертається до вихідного стану. Витрачено дві копії (парність не змінилась) і по одній копії кожної проблемної літери (їхня парність виправилась). Після цього виводимо всі решту літер відсортованими.

Для обгортки потрібна літера з запасом: \mathrm{cnt}_s[i] - \mathrm{cnt}_t[i] \ge 2. Позначимо множину таких літер через .

  • Якщо порожня — виправити парності нічим, відповідь NO.

  • Якщо |H| = 1, а єдина літера i \in H сама проблемна, то й вона не рятує: обгортка витрачає дві її копії й парність не змінює, а покласти всередину обгортки не можна — це передчасно закриє її. Відповідь NO.

  • Якщо |H| \ge 2, беремо i = H_1 як обгортку для всіх проблемних літер, крім самої , а потім другою обгорткою H_2 виправляємо парність , якщо вона проблемна.

Запасу вистачає завжди: якщо літера з проблемна, то її запас непарний і не менший за , отже не менший за , і після витрат обгорток лишається невід'ємним.

Складність — \mathcal{O}(|s| + |t| + 26).