То, что каждый символ перемещается не более чем на одну позицию, означает, что нам разрешается менять местами соседние символы, при этом каждый символ можно трогать не более одного раза.
Задача решается при помощи динамического программирования.
d[i][f1][f2], где ,
равно true, если можно получить строку, в которой префикс длины i совпадает с развёрнутым суффиксом длины i, при этом f1 означает, был ли последний символ этого префикса поменян местами со следующим за ним, f2 — был ли первый символ суффикса поменян местами с предыдущим.
d[i][f1][f2] вычисляется из d[i - 1][g1][g2] (g1, g2 перебираем). gj может быть true, только если fj = false. Этот переход в динамике можно сделать, только если последний символ префикса длины i и первый элемент суффикса длины j совпадут после свопов, которые задаются значениями fj, gj.
Если n чётно, то ответ — это d[n / 2][false][false].
Если n нечётно, то ответ — это d[⌊ n / 2⌋][false][false] or d[⌊ n / 2⌋][true][false] or d[⌊ n / 2⌋][false][true].