Сломанный крюк

Автор задачи: Антон Вдовин, разработчик: Егор Юлин

Для начала заметим, что нам достаточно рассматривать подстроки длины только $$$2$$$ или $$$3$$$. Действительно, пусть есть подстрока-палиндром большей длины, но тогда в ней точно есть подстрока-палиндром длины $$$2$$$ или $$$3$$$ (мы можем удалить одинаковое количество символов с концов, пока не получим необходимые длины).

Далее есть два решения. Рассмотрим решение, которое использует динамическое программирование.

В $$$\mathtt{dp}[i][f_1][f_2]$$$ будем хранить минимальное число изменений на префиксе длины $$$i$$$, где $$$f_1$$$ и $$$f_2$$$ — флаги того, были ли изменены последние два символа. Тогда если текущая позиция $$$i$$$, $$$s_i = s_{i-1}$$$ и символ на позиции $$$i-1$$$ не был изменен, мы должны поменять символ на позиции $$$i$$$. Аналогично с позицией $$$i-2$$$. Получается пересчет всей динамики за $$$\mathcal{O}(n)$$$.

Покажем, как восстанавливать ответ — это менее тривиально, чем просто посчитать динамику. Пусть мы знаем, что символ на позиции $$$i$$$ нужно заменить, тогда найдем любой символ, которого нет в подстроке $$$\overline{s_{i-2} s_{i-1} s_i s_{i+1} s_{i+2}}$$$, и присвоим в $$$s_i$$$ этот символ. Такой подход работает, так как в нам достаточно добиться отсутствия палиндромов длины $$$2$$$ и $$$3$$$, то есть необходимо и достаточно избавиться от повторяющихся символов в таких строках. Собственно, ровно этого мы и добиваемся такими заменами.