Задача:
Дана строка, требуется найти самую длинную подстроку, являющуюся палиндромом.
Решение:
Для поиска подстрок-палиндромов можно использовать следующий способ - начнем процесс поиска с центра строки. Для различных палиндромов центром может являться 1 либо 2 символа.
К примеру:
1) "роз узор" - центром является символ "у";
2) "барокко раб" - центром являются два символа "кк".
Для того, чтобы найти самый длинный палиндром с центром на произвольной позиции N, нужно произвести две проверки, для случаев 1 и 2.
1) Строка из одного символа сама по себе является палиндромом. Для того, чтобы выяснить, есть ли более длинный палиндром с центром в символе N, нужно начать сравнивать попарно символы на позициях [N-1, N+1], [N-2, N+2], и т. д. Продолжая сравнение таким образом до первой несовпадающей пары либо до границ строки, мы найдем самый длинный палиндром с центром в символе N.
2) Сравним символы N и N+1. Если они совпадают, у нас есть минимальный палиндром с центром в этих двух символах, размера 2.
Затем аналогично первому способу, начнем попарное сравнение [N-1, N+2], [N-2, N+3], и т. д.
Таким образом мы найдем самый длинный палиндром с центром в символах N и N+1
3) Проведя подобный поиск на каждой позиции исходной строки мы найдем самую длинную подстроку, являющуюся палиндромом.
Time complexity данного решения O(N^2). Статья о данном алгоритме на leetcode упоминает Алгоритм Манакера, который решает эту задачу за O(N). ИМХО, в контексте подготовки к интервью изучение данного алгоритма опционально.
Мое решение:
https://gist.github.com/codekrolik/80338e07438f2d2894dd
Тесты:
https://gist.github.com/codekrolik/24aaeb86085e4ae837c5