Для каждого места (буквы + расстояния между ними) будем проверять длину макс подпалиндрома с помощью бин поиска (его длину).
Осталось за О(1) проверить является ли эта подстрока палиндромом, что можно сделать с помощью хешей (заранее посчитать хэш для каждого префикса, и высчитывать хэш подстроки в обе стороны и сравнивать)