Спершу з'ясуємо, що робить унікалізація з відсортованим рядком.
Нехай усі однакові літери йдуть підряд. Перша a додається в , друга — виштовхує першу (стек повертається до попереднього стану), третя знову додається, і так далі. Отже, після обробки блоку з однакових літер ця літера залишається в тоді й лише тоді, коли непарне, а решта стека не змінюється.
Звідси головне спостереження:
Необхідні умови. Рядок завжди складається з різних літер, тому в не може бути повторів. Крім того, кожна літера мусить траплятися в . Якщо щось із цього порушено — відповідь 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).