Почему это работает
- Палиндром зеркален относительно своей середины. Значит, начинаем с середины и шагаем наружу, пока две буквы по краям совпадают.
- Середина — это буква, когда длина нечётная («aba»), и промежуток между двумя буквами, когда чётная («abba»). В строке из n букв n букв и n − 1 промежутков: 2n − 1 центров. Перебрав их все, не пропустим ни одного палиндрома.
- Рост останавливается на первой несовпавшей паре: любой кусок длиннее вокруг этого центра тоже содержит эту пару, значит, и он не палиндром.
Сложность
Время O(n²): 2n − 1 центров, и из каждого указатели делают не больше n / 2 шагов. Память O(1), не считая самого ответа: храним только start и end, а кусок вырезаем один раз в конце. Алгоритм Манакера находит ответ за O(n), но на собеседовании его ждут редко.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗