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

Решение:
Разберем решение за O(N^2)
Пусть dp[l][r] = 1 если подстрока [l, r] является палиндромом и 0 иначе. База дп будет dp[i][i] = 1 для всех i, а также dp[i][i + 1] = 1, если s[i] = s[i + 1].
Давайте научимся пересчитывать состояние dp, для этого переберем отрезки начиная с меньших длин. Пусть сейчас хотим узнать является ли палиндромом подстрока [l, r]. Замечу, что для подстроки [l + 1, r - 1] мы уже знаем является ли подстрока палиндромом или нет (потому что начинали перебирать подотрезки по возрастанию длин), очевидно если s[l] = s[r] и dp[l + 1][r - 1] = 1 то подстрока [l, r] будет палиндромом! В таком случае делаем dp[l][r] = 1.

Чтобы вывести саму подстроку мы перебираем подотрезки и обновляем ответ если подстрока палиндром, то есть dp[l][r] = 1 и длина подстроки наибольшая.

Решение за O(N) использовать алгоритм Манакера, который умеет находить все палиндромы в строке за O(N).
Псевдокод в комментариях: