5. Самая длинная подстрока-палиндром

Условие

Дана строка s. Нужно вернуть её самую длинную подстроку, которая является палиндромом, то есть одинаково читается слева направо и справа налево. Если таких подстрок несколько, подойдёт любая из них. (Условие LeetCode)

Подстрока состоит из подряд идущих символов: нельзя выбросить символ из середины и склеить оставшиеся. Например, в строке "abcda" две буквы "a" образуют подпоследовательность "aa", но не подстроку.

Примеры из условия: (LeetCode)

s = "babad"
Ответ: "bab"
"aba" тоже подходит.

s = "cbbd"
Ответ: "bb"

Длина строки от 1 до 1000, символы: английские буквы и цифры. (Ограничения LeetCode) Регистр не меняем: "Aa" не палиндром, потому что "A" и "a" различаются.

Идея

У палиндрома совпадают крайние символы, а внутри находится ещё один палиндром. На это свойство можно посмотреть с двух сторон:

• Снаружи внутрь: проверить крайние символы, затем сдвинуть оба указателя к середине. Так мы проверяем уже выбранную подстроку.
• Изнутри наружу: выбрать центр и расширяться, пока символы слева и справа совпадают. Так мы сразу строим палиндромы.

Для основного решения выберем второй взгляд. Затем посмотрим, как сохранить результаты для подстрок в таблице и как алгоритм Манакера переиспользует информацию между разными центрами.

Полный перебор

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

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best_start = 0
        best_len = 0

        for start in range(n):
            for end in range(start, n):
                left, right = start, end

                while left < right and s[left] == s[right]:
                    left += 1
                    right -= 1

                if left >= right and end - start + 1 > best_len:
                    best_start = start
                    best_len = end - start + 1

        return s[best_start:best_start + best_len]

Пар границ O(n²), проверка одной подстроки занимает до O(n). Итого O(n³) времени и O(1) дополнительной памяти без учёта результата.

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

Основное решение: расширение от центра

Вместо перебора двух границ переберём один центр. Для каждого центра будем двигать указатели в разные стороны, пока остаёмся в строке и видим одинаковые символы.

Почему нужны два типа центров

У палиндрома нечётной длины в центре находится символ, а у палиндрома чётной длины центр расположен между символами. Если проверять только первый вариант, мы пропустим, например, "bb" из второго примера.

Нечётная длина:

    b a b
      ^
   центр в a

Чётная длина:

    a b b a
       ^
 центр между b и b

Поэтому для каждого индекса i запускаем два расширения:

• Нечётный палиндром: начинаем с left = i, right = i.
• Чётный палиндром: начинаем с left = i, right = i + 1.

Второй вызов для последнего символа сразу остановится на границе. Отдельную проверку для этого случая писать не нужно.

Что возвращает расширение

Напишем функцию expand(left, right), которая возвращает границы найденного палиндрома как полуинтервал [start, end). Правая граница не включается, поэтому длина равна end - start, а подстрока записывается как s[start:end].

При успешном сравнении расширяем границы. Когда цикл остановится, указатели уже стоят за пределами последнего подтверждённого палиндрома, поэтому возвращаем left + 1, right.

Код на Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best_start = 0
        best_len = 0

        def expand(left: int, right: int) -> tuple[int, int]:
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1

            return left + 1, right

        for i in range(n):
            for left, right in ((i, i), (i, i + 1)):
                start, end = expand(left, right)
                length = end - start

                if length > best_len:
                    best_start = start
                    best_len = length

        return s[best_start:best_start + best_len]

Пока ищем ответ, храним только начало и длину. Сам срез создаём один раз в конце, а не при каждом успешном расширении.

Разбор примера

Возьмём s = "cbbd" и чётный центр между индексами 1 и 2. Сначала видим одинаковые "b", а после расширения упираемся в несовпадающие "c" и "d".

Индексы:  0 1 2 3
Строка:   c b b d
            L R       b == b, расширяемся

          c b b d
          L     R     c != d, останавливаемся

expand(1, 2) возвращает (1, 3).
s[1:3] == "bb", длина 2.

Для нечётного центра всё работает так же. Например, из центральной "a" в "babad" получаем сначала "a", затем "bab", после чего левый указатель выходит за границу строки.

Почему решение правильное

Каждый палиндром имеет один из двух рассмотренных типов центра. Для выбранного центра расширение не пропускает ни одной возможной пары символов: пока пара совпадает, палиндром можно увеличить, а первое несовпадение или граница строки не позволяет продолжить.

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

Сложность

Центров O(n), и для каждого расширение может занять O(n). Итого O(n²) времени и O(1) дополнительной памяти без учёта возвращаемой строки.

На "aaaa…a" многие центры дают длинные палиндромы, поэтому квадратичная оценка достижима. На строках, где расширения быстро обрываются, сравнений будет меньше, но худший случай остаётся квадратичным.

Альтернатива: динамическое программирование

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

В расширении от центра мы строили всё большие палиндромы вокруг одной точки. Можно иначе: хранить для каждой пары границ, является ли соответствующая подстрока палиндромом.

Состояние и переход

Пусть dp[left][right] означает, что подстрока от left до right включительно является палиндромом. Тогда достаточно совпадения крайних символов и одного из двух условий:

• Длина не больше трёх: внутри либо ничего нет, либо один символ, поэтому дополнительная проверка не нужна.
• Длина больше трёх: внутренняя подстрока уже должна быть палиндромом, то есть dp[left + 1][right - 1] == True.

В коде это выражается так:

s[left] == s[right]
и
(right - left <= 2 или dp[left + 1][right - 1])

Например, "aba" подходит сразу после сравнения двух "a", потому что внутри один символ. А для "abca" одинаковых краёв мало: внутренняя "bc" не палиндром.

Порядок заполнения

Состояние зависит от строки таблицы с индексом left + 1. Поэтому left перебираем справа налево: к моменту обработки текущей строки нужная нижняя строка таблицы уже готова.

Внутри перебираем right от left до конца. Короткие случаи обрабатываются первой частью or, и Python не обращается к внутренней подстроке, когда это не требуется.

Код на Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        best_start = 0
        best_len = 0

        for left in range(n - 1, -1, -1):
            for right in range(left, n):
                if s[left] == s[right] and (
                    right - left <= 2 or dp[left + 1][right - 1]
                ):
                    dp[left][right] = True
                    length = right - left + 1

                    if length > best_len:
                        best_start = left
                        best_len = length

        return s[best_start:best_start + best_len]

Переход корректен: совпадающие края и палиндром внутри дают палиндром целиком, а несовпадение хотя бы одного условия его исключает. Из корректности коротких случаев и выбранного порядка заполнения следует корректность всей таблицы.

Сложность и выбор подхода

Таблица содержит O(n²) ячеек, каждая вычисляется за O(1). Получаем O(n²) времени и O(n²) дополнительной памяти.

Для поиска только самой длинной подстроки я бы выбрал расширение от центра: время такое же, а таблица не нужна. Динамику полезно уметь вывести, особенно если дальше понадобятся проверки многих разных подстрок на палиндромность.

Алгоритм Манакера: линейное время

По моей оценке, Манакер по сложности понимания и реализации точно уровень Hard. Это оценка самого подхода, а не изменение официальной сложности задачи: не стоит считать, что для её понимания обязательно сразу самостоятельно вывести линейное решение.

Расширение от центра всё ещё повторяет работу: внутри уже найденного большого палиндрома мы заново проверяем маленькие. Манакер использует симметрию большого палиндрома, чтобы часть этих проверок пропустить. Именно переиспользование радиусов позволяет получить O(n) времени. (CP-Algorithms)

Ниже разберём вариант с разделителями. Он объединяет чётные и нечётные палиндромы в один случай; такой приём также описан в CP-Algorithms.

Убираем различие между чётной и нечётной длиной

Вставим # между символами и по краям строки. После этого центром любого исходного палиндрома становится конкретная позиция новой строки.

"aba"  →  "#a#b#a#"
"abba" →  "#a#b#b#a#"

У "aba" центр по-прежнему находится в "b". У "abba" центр теперь находится в # между двумя "b", поэтому обе строки обрабатываются одним и тем же расширением.

Обозначим преобразованную строку через t. Построим её с помощью join, чтобы не дописывать символы к растущей строке в цикле:

t = "#" + "#".join(s) + "#"

По ограничениям исходная строка содержит только буквы и цифры, поэтому # не встречается среди её символов. (LeetCode) Границы будем проверять явно, без дополнительных служебных символов по краям.

Что такое радиус

Пусть p[i] хранит радиус самого длинного палиндрома с центром i в строке t. Сам центр в радиус не включаем: палиндром занимает индексы от i - p[i] до i + p[i] включительно.

Например, у строки "#a#b#a#" центр i = 3, а радиус p[3] = 3. Длина палиндрома в t равна 2 * p[i] + 1, но длина соответствующего палиндрома в исходной строке равна p[i].

Почему получается именно так: исходный палиндром длины L после добавления разделителей имеет длину 2 * L + 1. Следовательно, его радиус без центрального символа равен L.

Какой большой палиндром запоминаем

Будем обрабатывать позиции t слева направо. Среди уже обработанных центров запомним палиндром, который заканчивается правее всех, а не обязательно самый длинный.

Для него храним две величины:

• center: центр этого палиндрома.
• right: индекс его последнего символа, включительно; right = center + p[center].

Самый длинный ответ храним отдельно в best_center и best_len. Эти задачи различаются: right помогает экономить сравнения, а best_len нужен для ответа.

Зеркальная позиция

Пусть новый индекс i находится строго левее right. Его зеркальная позиция относительно center вычисляется так:

mirror = 2 * center - i

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

Большой палиндром:

left ........ mirror ... center ... i ........ right
                  <------ равные расстояния ------>

mirror = center - (i - center)
       = 2 * center - i

Но нельзя безусловно присвоить p[i] = p[mirror]: зеркальный палиндром может выходить за границу большого. Симметрия за этой границей нам ничего не гарантирует, поэтому стартовый радиус ограничиваем:

p[i] = min(p[mirror], right - i)

Здесь right - i означает, сколько шагов вправо от i ещё остаётся внутри известного большого палиндрома. Это и есть предел информации, которую можно перенести без новых сравнений. (Разбор ограничения радиуса в CP-Algorithms)

После такого присваивания запускаем обычное расширение. Только начинаем не с нуля, а с первой ещё не подтверждённой пары: i - p[i] - 1 и i + p[i] + 1.

Если i >= right, полезного положительного радиуса из большого палиндрома не получить. Начинаем с p[i] = 0 и расширяемся обычным способом.

Пример переиспользования

Рассмотрим s = "abacaba". В преобразованной строке центральная "c" имеет индекс 7, радиус 7 и правую границу 14.

Индекс:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
t:       # a # b # a # c # a  #  b  #  a  #
                       ^
                    center = 7

Когда доходим до i = 9, зеркальная позиция равна 5. Для неё уже известно p[5] = 1, поэтому сразу получаем p[9] = min(1, 14 - 9) = 1, не перепроверяя пару разделителей вокруг "a".

Для i = 11 зеркало находится в 3, где p[3] = 3. Получаем стартовый радиус min(3, 14 - 11) = 3: маленький палиндром "#a#b#a#" уже подтверждён симметрией большого.

Обрати внимание на ещё один возможный случай: если радиус зеркала равен 5, а до right осталось только 3, переносим лишь 3. Оставшиеся пары обязательно проверяем заново, потому что они находятся за пределами известного большого палиндрома.

Код на Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = "#" + "#".join(s) + "#"
        m = len(t)
        p = [0] * m

        center = 0
        right = 0
        best_center = 0
        best_len = 0

        for i in range(m):
            if i < right:
                mirror = 2 * center - i
                p[i] = min(p[mirror], right - i)

            while (
                i - p[i] - 1 >= 0
                and i + p[i] + 1 < m
                and t[i - p[i] - 1] == t[i + p[i] + 1]
            ):
                p[i] += 1

            if i + p[i] > right:
                center = i
                right = i + p[i]

            if p[i] > best_len:
                best_center = i
                best_len = p[i]

        start = (best_center - best_len) // 2
        return s[start:start + best_len]

Здесь right всегда включительная граница. Если в другой реализации right обозначает первую позицию за палиндромом или радиус включает центр, формулы будут отличаться: нельзя переносить их по одной, не проверив соглашения.

Как восстановить ответ

Левая граница найденного палиндрома в t равна best_center - best_len. В преобразованной строке перед каждым исходным символом добавлен разделитель, поэтому начало в s получаем делением на два:

start = (best_center - best_len) // 2

Длина в исходной строке уже равна best_len. Например, для "abba" центр в t равен 4, радиус тоже 4, поэтому start = (4 - 4) // 2 = 0, а ответ равен s[0:4].

Почему решение правильное

Перед обработкой i радиусы всех предыдущих центров уже найдены точно. Если i внутри известного большого палиндрома, симметрия гарантирует палиндром радиуса min(p[mirror], right - i); если снаружи, единственная начальная гарантия заключается в самом центральном символе.

Дальше проверяем все следующие пары до первого несовпадения или границы строки. Значит, находим точный максимальный радиус для i, после чего корректно обновляем самый правый палиндром и лучший ответ.

Так последовательно получаем правильные радиусы для всех центров. Любой исходный палиндром представлен в t, поэтому максимум радиусов даёт искомую самую длинную подстроку.

Почему время линейное, хотя внутри есть while

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

• Зеркальный радиус меньше right - i: маленький палиндром целиком помещается внутри большого, вместе со следующей несовпадающей парой. По симметрии эта пара не совпадёт и справа, поэтому while не сделает ни одного успешного расширения.
• Зеркальный радиус не меньше right - i: стартовый радиус уже доходит до right. Каждое последующее успешное расширение подтверждает новую позицию правее прежней границы.

Если i вне большого палиндрома, каждое успешное расширение тоже проходит правее прежней границы. После обработки центра right обновляется до достигнутой позиции и никогда не уменьшается.

Всего новых позиций справа не больше m = 2 * n + 1, значит, успешных расширений O(n). Неуспешных проверок, завершающих цикл, не больше одной на центр, и их тоже O(n). Именно такое суммарное рассуждение лежит в основе линейной оценки Манакера. (CP-Algorithms)

Построение t, проход по центрам и создание ответа также занимают линейное время. Итого O(n) времени и O(n) дополнительной памяти для преобразованной строки и массива радиусов.

Что важно не перепутать

• Подстрока и подпоследовательность: здесь нельзя удалять символы из середины. Алгоритм для самой длинной палиндромной подпоследовательности решает другую задачу.
• Чётные палиндромы: без центров между символами решение пропустит "bb" и "abba". В Манакере эту роль выполняют центры на разделителях.
• Границы после расширения: в основном решении указатели останавливаются снаружи палиндрома. Поэтому возвращаем [left + 1, right), а не [left, right].
• Срезы в цикле: s[left:right + 1] создаёт строку, а не просто обозначает границы. Если создавать такой срез при каждом расширении и затем вычислять его длину, можно превратить квадратичное решение в кубическое.
• Одинаковые по длине ответы: условие допускает любой максимальный палиндром. Не нужно требовать именно "bab", если решение вернуло "aba" для "babad". (LeetCode)
• Граница Манакера: right относится к палиндрому, который заканчивается правее всех, а не обязательно к текущему самому длинному ответу. Смешивание этих двух величин ломает переиспользование радиусов.

Сравнение подходов

В таблице дополнительная память указана без возвращаемой строки. Её создание в Python требует до O(n) времени и памяти для всех четырёх реализаций и не меняет итоговые оценки времени.

Как рассказать на собеседовании

Я бы начал с полного перебора, показал повторяющуюся работу, а затем предложил расширение от центра. Это короткое решение с понятным доказательством, без таблицы и сложных соглашений об индексах.

Если попросят линейное время, переход к Манакеру можно объяснить так: «Мы уже нашли большой палиндром. Центры внутри него имеют зеркальные позиции, для которых радиусы известны, поэтому часть сравнений можно не повторять».

В официальном Editorial Манакер приведён для полноты, при этом авторы отдельно отмечают, что подробное изучение этого алгоритма выходит за рамки обычных собеседований. (Editorial LeetCode) Это не запрет изучать его: полезнее понять симметрию и движение правой границы, чем запомнить формулу без объяснения.

Вывод

Ключевой переход в задаче: не проверять все возможные границы, а строить палиндромы из центра. Это сразу даёт понятное квадратичное решение с постоянной дополнительной памятью.

Манакер делает следующий шаг: внутри уже известного палиндрома использует зеркальные радиусы и сравнивает заново только то, что нельзя гарантировать симметрией. За счёт этого правая граница продвигается суммарно лишь линейное число раз.