Longest Palindromic Substring (LeetCode 5): перебор, ДП и расширение от центра

Разбор LeetCode 5 и 647: самая длинная палиндромная подстрока и подсчёт палиндромов. Перебор, ДП за O(n²), расширение от центра с O(1) памяти и что ждут на собеседовании.

8 мин чтенияалгоритмы · строки · динамическое программирование · python

Коротко

ПодходВремяПамятьКогда говорить на собеседовании
Перебор всех подстрокO(n3)O(n^3)O(1)O(1)Как стартовую точку, одной фразой
ДП по таблице dp[i][j]O(n2)O(n^2)O(n2)O(n^2)Если интервьюер просит именно ДП
Расширение от центраO(n2)O(n^2)O(1)O(1)Основное решение — его и пишут
Алгоритм МанакераO(n)O(n)O(n)O(n)Упомянуть; писать — только если попросят
  • Главная идея: у любого палиндрома есть центр — символ (aba) или промежуток между символами (abba). Центров всего 2n−12n - 1, от каждого расширяемся, пока края совпадают.
  • Та же техника почти без изменений решает LeetCode 647 Palindromic Substrings — подсчёт всех палиндромных подстрок.
  • Типичная ошибка — забыть чётные палиндромы. Вторая по частоте — «развернуть строку и найти общую подстроку».

Постановка задачи

LeetCode 5. Longest Palindromic Substring. Дана строка s. Верните самую длинную подстроку, которая является палиндромом — читается одинаково слева направо и справа налево.

Вход:  s = "babad"
Выход: "bab"        # "aba" тоже правильный ответ

Вход:  s = "cbbd"
Выход: "bb"

Ограничения: 1 <= s.length <= 1000, строка состоит из цифр и латинских букв.

Сразу отметим две вещи, которые стоит проговорить вслух в начале интервью:

  1. Подстрока, а не подпоследовательность. Символы идут подряд. Для подпоследовательности есть отдельная задача — LeetCode 516 Longest Palindromic Subsequence, и решается она другим ДП.
  2. Ответов может быть несколько. Для "babad" подходят и "bab", и "aba" — возвращать можно любой. Уточните это у интервьюера, чтобы не тратить время на «правильный» выбор.

Ограничение n≤1000n \le 1000 — тоже подсказка: решение за O(n2)O(n^2) — это около миллиона операций, оно проходит спокойно. От вас не ждут линейного алгоритма.

Решение 1: перебор

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

def longest_palindrome_brute(s: str) -> str: best = "" n = len(s) for i in range(n): for j in range(i + len(best), n): # короче best проверять незачем sub = s[i:j + 1] if sub == sub[::-1]: best = sub return best

Подстрок O(n2)O(n^2), проверка каждой — O(n)O(n), итого O(n3)O(n^3). Отсечение i + len(best) помогает на практике, но асимптотику не меняет.

На собеседовании это решение не пишут целиком. Достаточно сказать: «Наивно — перебрать все O(n2)O(n^2) подстрок и проверить каждую за O(n)O(n), получится кубическая сложность. Давайте заметим, что проверки повторяются». Это мостик к следующим двум решениям.

Решение 2: динамическое программирование

Где здесь повторяющаяся работа

Когда мы проверяем s[i..j], мы фактически сравниваем s[i] с s[j], а потом проверяем s[i+1..j-1]. Но s[i+1..j-1] мы уже проверяли раньше — это более короткая подстрока. Отсюда рекуррентное соотношение:

dp[i][j]=(si=sj)∧(j−i<2∨dp[i+1][j−1])dp[i][j] = (s_i = s_j) \land \big(j - i < 2 \lor dp[i+1][j-1]\big)

Словами: s[i..j] — палиндром, если крайние символы равны и внутренняя часть — палиндром. Базовые случаи — подстроки длины 1 (всегда палиндромы) и длины 2 (палиндром, если два символа равны). Условие j - i < 2 их и покрывает.

Подробнее о том, как вообще выводить такие переходы, — в статье Динамическое программирование для начинающих. Эта задача — классический пример ДП по отрезкам: состояние — отрезок [i, j], переход — к отрезку поменьше.

Порядок обхода

Это самое скользкое место. dp[i][j] зависит от dp[i+1][j-1] — от отрезка, который короче на 2. Значит, считать нужно так, чтобы короткие отрезки были готовы раньше длинных. Проще всего перебирать длину:

def longest_palindrome_dp(s: str) -> str: n = len(s) if n < 2: return s # dp[i][j] == True, если s[i..j] — палиндром dp = [[False] * n for _ in range(n)] start, max_len = 0, 1 for i in range(n): dp[i][i] = True # перебираем длину подстроки: короткие считаются раньше длинных for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] != s[j]: continue if length == 2 or dp[i + 1][j - 1]: dp[i][j] = True if length > max_len: start, max_len = i, length return s[start:start + max_len]

Если написать наивное for i in range(n): for j in range(i, n), то в момент вычисления dp[i][j] строка i + 1 ещё не посчитана — и ответ будет неверным. Альтернатива перебору по длине — идти по i с конца: for i in range(n - 1, -1, -1), тогда строка i + 1 уже готова. Этот вариант мы используем ниже в задаче 647.

Сложность

Время O(n2)O(n^2), память O(n2)O(n^2): таблица 1000×10001000 \times 1000 — это миллион ячеек. В Python список списков такого размера занимает несколько мегабайт и заметно медленнее, чем следующее решение.

Улучшить память у этого ДП можно, но неудобно: зависимость идёт по диагонали. Поэтому на практике сразу переходят к расширению от центра — оно даёт ту же асимптотику по времени и O(1)O(1) памяти.

Решение 3: расширение от центра

Интуиция

Посмотрим на палиндром с другой стороны — не снаружи внутрь, как в ДП, а изнутри наружу. У каждого палиндрома есть центр:

  • у нечётного (racecar) — символ посередине, e;
  • у чётного (abba) — промежуток между двумя b.

Если s[l..r] — палиндром и s[l-1] == s[r+1], то s[l-1..r+1] — тоже палиндром. Значит, можно встать в центр и раздвигать границы, пока символы по краям совпадают. Как только не совпали — дальше от этого центра палиндромов нет.

Центров в строке длины nn ровно 2n−12n - 1: nn символов и n−1n - 1 промежутков. Перебираем их все.

Код

def longest_palindrome(s: str) -> str: def expand(left: int, right: int) -> int: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return right - left - 1 # длина палиндрома s[left+1 .. right-1] start, max_len = 0, 0 for center in range(len(s)): odd = expand(center, center) # центр — символ: "aba" even = expand(center, center + 1) # центр — между символами: "abba" length = max(odd, even) if length > max_len: max_len = length start = center - (length - 1) // 2 return s[start:start + max_len]

Два места, где легко ошибиться.

Длина после цикла. Цикл останавливается, когда s[left] != s[right] или вышли за границы. То есть последние валидные границы — left + 1 и right - 1, а длина — (right - 1) - (left + 1) + 1 = right - left - 1.

Начало палиндрома. Зная центр и длину, начало считаем как center - (length - 1) // 2. Проверим на обоих случаях:

  • "aba", центр 1, длина 3: 1 - (3 - 1) // 2 = 0 — верно;
  • "abba", центр 1 (промежуток между индексами 1 и 2), длина 4: 1 - (4 - 1) // 2 = 1 - 1 = 0 — тоже верно.

Формула (length - 1) // 2 работает для обеих чётностей сразу, поэтому отдельные ветки не нужны. Если не уверены в арифметике на интервью — пусть expand возвращает сами границы (left + 1, right - 1), а не длину. Это на пару символов длиннее, зато ошибиться негде.

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

Строка s = "cbbd":

centerнечётный expand(c, c)чётный expand(c, c+1)лучший на шаге
0c → 1c ≠ b → 0"c"
1b → 1b = b, затем c ≠ d → 2"bb"
2b → 1b ≠ d → 0"bb"
3d → 1вышли за границу → 0"bb"

Ответ — "bb". Без чётной проверки получили бы "c": именно на этом тесте падают решения, где забыли про чётные палиндромы.

Сложность

  • Время — O(n2)O(n^2) в худшем случае. Худший случай — строка из одинаковых символов "aaaa…a": от центра в середине расширяемся почти на всю строку. На случайных строках расширение обрывается через пару шагов, и решение работает почти линейно.
  • Память — O(1)O(1), не считая ответа.

Вот почему это решение — основное. Оно короче ДП, не требует таблицы и реально быстрее. В нашем локальном замере на CPython строку из 1000 случайных букв a/b расширение обработало в десятки раз быстрее табличного ДП; на строке из 1000 одинаковых букв (худший случай) разница сократилась примерно до двух раз, но расширение всё равно впереди.

Та же версия на JavaScript

function longestPalindrome(s) { let start = 0 let maxLen = 0 const expand = (left, right) => { while (left >= 0 && right < s.length && s[left] === s[right]) { left-- right++ } return right - left - 1 } for (let center = 0; center < s.length; center++) { const len = Math.max(expand(center, center), expand(center, center + 1)) if (len > maxLen) { maxLen = len start = center - Math.floor((len - 1) / 2) } } return s.slice(start, start + maxLen) } console.log(longestPalindrome('babad')) // bab console.log(longestPalindrome('cbbd')) // bb

Обратите внимание на Math.floor: в JavaScript / даёт дробь, и без округления вниз start станет нецелым.

Решение 4: алгоритм Манакера, коротко

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

Подробный разбор с кодом и визуализацией — в отдельной статье Алгоритм Манакера. Здесь важно другое: что говорить на собеседовании.

  • Для LeetCode 5 при n≤1000n \le 1000 линейный алгоритм не нужен. Интервьюер почти всегда ждёт расширение от центра.
  • Хороший ход — после написанного решения сказать: «Существует алгоритм Манакера за O(n)O(n), он переиспользует симметрию уже найденных палиндромов». Это показывает кругозор и не тратит время.
  • Писать Манакера по памяти стоит, только если об этом прямо попросят. Код короткий, но в нём легко ошибиться с индексами, а на интервью ошибка в «продвинутом» решении хуже, чем чистое O(n2)O(n^2).

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

Типичная ловушка: развернуть строку и найти общую подстроку

Кажется логичным: палиндром совпадает со своим разворотом, значит, ответ — самая длинная общая подстрока s и reversed(s). Это неверно.

Контрпример — s = "abacdfgdcaba". Разворот — "abacdgfdcaba". Самая длинная общая подстрока у них "abacd", но это не палиндром. Правильный ответ — "aba".

Проблема в том, что "abacd" встречается в начале s и, в развёрнутом виде, в конце s — это два разных куска, а не один и тот же. Подход можно спасти, проверяя, что индексы совпадений соответствуют одной позиции в исходной строке, но получается сложнее и медленнее, чем расширение от центра. Если кандидат предлагает этот путь, интервьюер обычно просит контрпример — полезно знать его заранее.

LeetCode 647: Palindromic Substrings

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

Вход:  s = "abc"
Выход: 3          # "a", "b", "c"

Вход:  s = "aaa"
Выход: 6          # "a", "a", "a", "aa", "aa", "aaa"

Ограничения: 1 <= s.length <= 1000, строчные латинские буквы.

Расширение от центра

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

def count_substrings(s: str) -> int: def expand(left: int, right: int) -> int: count = 0 while left >= 0 and right < len(s) and s[left] == s[right]: count += 1 left -= 1 right += 1 return count total = 0 for center in range(len(s)): total += expand(center, center) total += expand(center, center + 1) return total

Время O(n2)O(n^2), память O(1)O(1). Здесь асимптотику O(n2)O(n^2) не улучшить перечислением: в строке "aaa…a" палиндромных подстрок n(n+1)2\frac{n(n+1)}{2}, и если считать их по одной, меньше квадрата не выйдет. Манакер решает и эту задачу за O(n)O(n) — он сразу знает радиус каждого центра и складывает радиусы, не перебирая палиндромы поштучно.

Через ДП

Та же таблица, что и в задаче 5, только вместо отслеживания максимума считаем все True. Для разнообразия — обход по i с конца:

def count_substrings_dp(s: str) -> int: n = len(s) dp = [[False] * n for _ in range(n)] total = 0 for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]): dp[i][j] = True total += 1 return total

Строка i + 1 к моменту обработки строки i уже посчитана — поэтому порядок корректный. Время и память — O(n2)O(n^2).

Обе задачи удобно решать в паре: если на интервью дали одну, вторую часто спрашивают как follow-up — «а теперь посчитайте их все».

Родственные задачи

Таблица dp[i][j] из решения 2 кажется проигрышной для задачи 5, но она пригождается там, где нужно много раз спрашивать «палиндром ли s[i..j]». Классический пример — LeetCode 131 Palindrome Partitioning: разбить строку на палиндромы всеми способами. Это бэктрекинг, и без предподсчёта каждая проверка куска стоит O(n)O(n). С таблицей — O(1)O(1):

def partition(s: str) -> list[list[str]]: n = len(s) # та же таблица, что в задаче 5: is_pal[i][j] — палиндром ли s[i..j] is_pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]) result, path = [], [] def backtrack(start: int) -> None: if start == n: result.append(path[:]) return for end in range(start, n): if is_pal[start][end]: # проверка за O(1) вместо O(n) path.append(s[start:end + 1]) backtrack(end + 1) path.pop() backtrack(0) return result print(partition("aab")) # [['a', 'a', 'b'], ['aa', 'b']]

Ещё несколько задач того же семейства:

  • LeetCode 132 Palindrome Partitioning II — минимальное число разрезов. Та же таблица is_pal плюс одномерное ДП по префиксам: cuts[j] = min(cuts[i - 1] + 1) по всем i, для которых s[i..j] — палиндром.
  • LeetCode 516 Longest Palindromic Subsequence — подпоследовательность вместо подстроки. ДП по отрезкам, но хранится уже длина, а не флаг.
  • LeetCode 214 Shortest Palindrome — дописать символы в начало, чтобы получился палиндром. Нужен самый длинный палиндромный префикс, и здесь O(n2)O(n^2) уже мало: решают через префикс-функцию, Z-функцию или Манакера.

Если вы поняли расширение от центра и таблицу dp[i][j], все эти задачи сводятся к знакомым кирпичикам.

Типичные ошибки

  1. Забыли чётные палиндромы. Расширяются только от символов, и "cbbd" даёт "c" вместо "bb". Лечится вторым вызовом expand(center, center + 1).
  2. Ошибка на единицу в длине. После цикла left и right уже указывают за пределы палиндрома. Длина — right - left - 1, а не right - left + 1.
  3. Неправильный порядок обхода в ДП. Внешний цикл по i от 0 к n - 1 обращается к ещё не посчитанной строке i + 1. Нужен обход по длине или по i с конца.
  4. Подпоследовательность вместо подстроки. Если в формулировке «subsequence» — это LeetCode 516, там переход dp[i][j] = max(dp[i+1][j], dp[i][j-1]) при несовпадении краёв.
  5. Срезы в цикле. В Python проверка s[i:j] == s[i:j][::-1] внутри двойного цикла — это скрытый третий множитель O(n)O(n). В переборе это ожидаемо, но в «оптимальном» решении срезов внутри циклов быть не должно.
  6. Целочисленное деление в JavaScript. (len - 1) / 2 без Math.floor даёт дробный индекс.

Как это выглядит на собеседовании

Задача популярна: она входит в большинство известных подборок вроде Blind 75 и NeetCode 150 и встречается на интервью в крупных компаниях. Хороший ход разговора обычно такой:

  1. Уточнить условие — подстрока или подпоследовательность, любой ли ответ подходит при равной длине, что вернуть для строки из одного символа.
  2. Назвать перебор за O(n3)O(n^3) и сразу объяснить, где в нём повторяющаяся работа.
  3. Предложить идею центра: «У каждого палиндрома есть центр, их 2n−12n - 1, от каждого расширяемся». Можно упомянуть ДП как альтернативу с O(n2)O(n^2) памятью.
  4. Написать расширение от центра — 15 строк кода.
  5. Прогнать на примерах "babad", "cbbd", "a", "aaaa" — последний проверяет чётный случай и худшую сложность.
  6. Назвать сложность O(n2)O(n^2) / O(1)O(1) и упомянуть Манакера за O(n)O(n).

Если вы только начинаете готовиться к задачам на строки, начните с Valid Palindrome — там та же проверка двумя указателями, но снаружи внутрь. Общий обзор строковых задач — в статье задачи на строки на собеседовании, а сама техника встречных указателей подробно разобрана в статье про два указателя.

Потренироваться в спокойной обстановке

Все задачи