У задачі йдеться про найдовший підпаліндром, тобто підпослідовність (символи не обов'язково поспіль), яка є паліндромом. Це класична задача динамічного програмування.
Для рядка довжини позначимо \mathrm{dp}[i][j] — довжину найдовшого підпаліндрому підрядка s_i \ldots s_j. Тоді
\mathrm{dp}[i][i] = 1;
якщо s_i = s_j, то крайні символи вигідно взяти обидва: \mathrm{dp}[i][j] = \mathrm{dp}[i+1][j-1] + 2;
інакше хоча б один із крайніх символів не входить у відповідь: \mathrm{dp}[i][j] = \max(\mathrm{dp}[i+1][j],\; \mathrm{dp}[i][j-1]).
Стани заповнюємо в порядку зростання довжини підрядка (або рекурсією з мемоізацією). Відповідь для всього рядка — .
Корисний альтернативний погляд: найдовший підпаліндром рядка — це найдовша спільна підпослідовність та оберненого .
У цій задачі запитів k \le 10, а довжина рядка не перевищує . Тому найпростіше на кожен запит вирізати підрядок s_l \ldots s_r і запустити для нього динаміку з нуля: це \mathcal{O}(k \cdot n^2), тобто щонайбільше 10^5 операцій.
Не забудьте, що індекси в умові нумеруються з одиниці.