Для данной строки s вернуть самую длинную палиндромную подстроку. Палиндромная подстрока — это подстрока, являющаяся палиндромом.
Самый длинный палиндром: решение
Решение с применением “грубой силы” состоит в том, чтобы просмотреть каждую подстроку в нашей строке и проверить, является ли она палиндромом или нет.
Количество подстрок растет квадратично с размером входной строки (O(n^2)). Проверка строки на предмет того, является ли она палиндромом, растет линейно.
Следовательно, такое решение займет O(n^3) времени.
Вместо этого мы можем просмотреть каждый символ в нашей строке и предположить, что это середина нашего палиндрома. Затем мы устанавливаем два указателя слева и справа от этого символа и смотрим, какой самый длинный палиндром образуется с центром на этом символе. Нам придется проверять палиндромы как четной, так и нечетной длины.
После того, как мы перебрали всю строку, мы можем вернуть самый длинный палиндром.
Временная сложность O(n^2).
