Могу подтолкнуть, вначале используя позиционный хеш, считаем его для всей строки за О(n). Потом простыми арифметическими манипуляциями можно получить его для любой подстроки за O(1). Делаем обход по строке и фиксируем центр палиндрома(стоит не забывать что длина палиндрома может быть чётной или нечётной), далее используя бинарный поиск ищем длину палиндрома(очевидно что если мы найдем палиндром длины 4, то не исключено что если добавить по 2 символа с обеих сторон, может получиться тоже палиндром).
Если нужен код могу скинуть, но я не фанат такого ;)
Я в своё время учил ДП по этому сайту Дистанционная подготовка, там много полезной теории для новичков, а главное есть задачи на которых ей можно проверить и проверочная система.
Такую задачу можно решить быстрее не за N^2 и без дополнительной памяти, а за NlogN, использую бинарный поиск + хеши ;) Если интересно могу написать решение.
Если нужен код могу скинуть, но я не фанат такого ;)