Задача Яндекса.
Дается строка, найти наибольший палиндромную подстроку.

Давно такая задача не встречалась на собесах, но недавно дали на собесе в яндекс.
Решение:

Наверное самое тупое решение - это зафиксировать длину подотрезка, пусть это число len. Теперь надо перебрать начало отрезка длины len, то есть зафиксировать [i, i + len - 1]. После нужно проверить правда ли этот подотрезок палиндром. Такое решение займет O(n^3) времени.

Скорее всего после такого решения вас не позовут дальше.....
Теперь обсудим решение, которое примут.
Переберем длину подотрезка len, после переберем начало подотрезка.
То есть зафиксировав len и i, мы получим отрезок [i, i + len - 1]. Остается вопрос, а как узнать правда ли подотрезок палиндром.
Во первых необходимо, что буквы s[i] и s[i + len - 1] были равны (иначе подотрезок точно не палиндром)
Во вторых нам важно чтобы подотрезок [i + 1, i + len - 2] был палиндром.
Если мы рассматриваем подотрезки по возрастанию длин (то есть по len), то по факту информацию о том, что подотрезок [i + 1, i + len - 2] является палиндромом, мы уже давно посчитали.
Пусть dp[l][r] = 1 если отрезок [l, r] палиндром.
В таком случае мы говорим, что dp[i][i + len - 1] = 1, если s[i] == s[i + len - 1] и dp[i + 1][i + len - 2] = 1.

Время работы алгоритма O(n^2).

Код в комментариях.

Эту задачу видел в Yandex Leetcode. Так что, если вы готовитесь к собеседованию, то имеет смысл прорешать Yandex Leetcode.

Также мы запускаем два курса по алгоритмам.
Если задачи на БП, два указателя, одномерные дпшки для тебя простые, то на продвинутом курсе по алгоритмам мы прорешаем ~200 задач на БОР, ДП по поддеревьям, игры и стратегии, bit manipulation.....

Если ты новичок в алгоритмах и хочешь хорошенько подтянуть за лето алгоритмы то тебе стоит взять основной курс по алгоритмам.