Я решал динамикой d[сколько прошли указов][предпоследний взятый указ][последний взятый указ]. Переход за O(1) — берем указ / не берем.

Предположим, что число в инпуте длиной n равно сумме двух зеркальных чисел длиной тоже n. Тогда мы знаем сумму первой и последней цифры ответа — она равна последней цифре числа из инпута (так как мы знаем, что переноса разряда не было). Отнимем эту сумму в двух местах — в начале и в конце, а на место первой и последней цифры в ответе поставим любые две, которые дают такую сумму. По сути, мы перешли к задаче меньшего на 2 размера.

Аналогично предположим, что число из инпута — сумма чисел длины n-1. Тогда мы знаем сумму первой и последней цифры с учётом, что перенос разряда был. И так далее, и тому подобное.

Невозможность проверяется, к примеру, выходом суммы на каком-то шаге за границы [0 + 0..9 + 9].

При добавлении символа в конец строки, добавляется не более одного нового палиндрома: пусть длина наидлиннейшего палиндрома, который является суффиксом строки S, равна X, тогда все палиндромы-суффиксы меньшей длины уже встречались в строке S без последнего символа в позиции |**S**| — X