Знайдемо всі «зіпсовані» позиції: такі i < n/2, для яких s_i \ne s_{n-1-i} (нумерація з нуля). Позначимо їх кількість через . Оскільки один обмін зачіпає щонайбільше дві пари, відповідь залежить саме від .
k = 0. Рядок уже паліндром — виводимо YES.
k = 1. Є рівно одна зіпсована пара , причому x \ne y. Виправити її, обмінявши символи всередині пари, неможливо — вони просто поміняються місцями. Єдиний шанс — задіяти середній символ, а він існує лише при непарному . Нехай середній символ дорівнює . Обмінявши його з одним із двох символів пари, ми зробимо пару однаковою тоді й лише тоді, коли збігається з або з . Отже, відповідь YES саме за цієї умови.
k = 2. Нехай зіпсовані пари — це та . Один обмін має виправити обидві одразу. Перебравши, які саме два символи міняються місцями, отримуємо просту умову: обидві пари виправляються тоді й лише тоді, коли
тобто коли мультимножини та збігаються.
k \ge 3. Один обмін виправляє не більше двох пар, тому відповідь NO.
Складність — , достатньо одного проходу по половині рядка.