Задачи с собеседований: самый длинный палиндром в строке

Для данной строки s вернуть самую длинную палиндромную подстроку. Палиндромная подстрока — это подстрока, являющаяся палиндромом.

Самый длинный палиндром: решение

Решение с применением “грубой силы” состоит в том, чтобы просмотреть каждую подстроку в нашей строке и проверить, является ли она палиндромом или нет.

Количество подстрок растет квадратично с размером входной строки (O(n^2)). Проверка строки на предмет того, является ли она палиндромом, растет линейно. 

Следовательно, такое решение займет O(n^3) времени.

Вместо этого мы можем просмотреть каждый символ в нашей строке и предположить, что это середина нашего палиндрома. Затем мы устанавливаем два указателя слева и справа от этого символа и смотрим, какой самый длинный палиндром образуется с центром на этом символе. Нам придется проверять палиндромы как четной, так и нечетной длины.

После того, как мы перебрали всю строку, мы можем вернуть самый длинный палиндром.

Временная сложность O(n^2).

Эта задача на LeetCode

← Еще задачи с собеседований