Longest Palindromic Substring (LeetCode 5): перебор, ДП и расширение от центра
Разбор LeetCode 5 и 647: самая длинная палиндромная подстрока и подсчёт палиндромов. Перебор, ДП за O(n²), расширение от центра с O(1) памяти и что ждут на собеседовании.
Коротко
| Подход | Время | Память | Когда говорить на собеседовании |
|---|---|---|---|
| Перебор всех подстрок | Как стартовую точку, одной фразой | ||
ДП по таблице dp[i][j] | Если интервьюер просит именно ДП | ||
| Расширение от центра | Основное решение — его и пишут | ||
| Алгоритм Манакера | Упомянуть; писать — только если попросят |
- Главная идея: у любого палиндрома есть центр — символ (
aba) или промежуток между символами (abba). Центров всего , от каждого расширяемся, пока края совпадают. - Та же техника почти без изменений решает LeetCode 647 Palindromic Substrings — подсчёт всех палиндромных подстрок.
- Типичная ошибка — забыть чётные палиндромы. Вторая по частоте — «развернуть строку и найти общую подстроку».
Постановка задачи
LeetCode 5. Longest Palindromic Substring. Дана строка s. Верните самую длинную подстроку, которая является палиндромом — читается одинаково слева направо и справа налево.
Вход: s = "babad"
Выход: "bab" # "aba" тоже правильный ответ
Вход: s = "cbbd"
Выход: "bb"
Ограничения: 1 <= s.length <= 1000, строка состоит из цифр и латинских букв.
Сразу отметим две вещи, которые стоит проговорить вслух в начале интервью:
- Подстрока, а не подпоследовательность. Символы идут подряд. Для подпоследовательности есть отдельная задача — LeetCode 516 Longest Palindromic Subsequence, и решается она другим ДП.
- Ответов может быть несколько. Для
"babad"подходят и"bab", и"aba"— возвращать можно любой. Уточните это у интервьюера, чтобы не тратить время на «правильный» выбор.
Ограничение — тоже подсказка: решение за — это около миллиона операций, оно проходит спокойно. От вас не ждут линейного алгоритма.
Решение 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
Подстрок , проверка каждой — , итого . Отсечение i + len(best) помогает на практике, но асимптотику не меняет.
На собеседовании это решение не пишут целиком. Достаточно сказать: «Наивно — перебрать все подстрок и проверить каждую за , получится кубическая сложность. Давайте заметим, что проверки повторяются». Это мостик к следующим двум решениям.
Решение 2: динамическое программирование
Где здесь повторяющаяся работа
Когда мы проверяем s[i..j], мы фактически сравниваем s[i] с s[j], а потом проверяем s[i+1..j-1]. Но s[i+1..j-1] мы уже проверяли раньше — это более короткая подстрока. Отсюда рекуррентное соотношение:
Словами: 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.
Сложность
Время , память : таблица — это миллион ячеек. В Python список списков такого размера занимает несколько мегабайт и заметно медленнее, чем следующее решение.
Улучшить память у этого ДП можно, но неудобно: зависимость идёт по диагонали. Поэтому на практике сразу переходят к расширению от центра — оно даёт ту же асимптотику по времени и памяти.
Решение 3: расширение от центра
Интуиция
Посмотрим на палиндром с другой стороны — не снаружи внутрь, как в ДП, а изнутри наружу. У каждого палиндрома есть центр:
- у нечётного (
racecar) — символ посередине,e; - у чётного (
abba) — промежуток между двумяb.
Если s[l..r] — палиндром и s[l-1] == s[r+1], то s[l-1..r+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) | лучший на шаге |
|---|---|---|---|
| 0 | c → 1 | c ≠ b → 0 | "c" |
| 1 | b → 1 | b = b, затем c ≠ d → 2 | "bb" |
| 2 | b → 1 | b ≠ d → 0 | "bb" |
| 3 | d → 1 | вышли за границу → 0 | "bb" |
Ответ — "bb". Без чётной проверки получили бы "c": именно на этом тесте падают решения, где забыли про чётные палиндромы.
Сложность
- Время — в худшем случае. Худший случай — строка из одинаковых символов
"aaaa…a": от центра в середине расширяемся почти на всю строку. На случайных строках расширение обрывается через пару шагов, и решение работает почти линейно. - Память — , не считая ответа.
Вот почему это решение — основное. Оно короче ДП, не требует таблицы и реально быстрее. В нашем локальном замере на 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: алгоритм Манакера, коротко
Расширение от центра делает лишнюю работу: если мы уже нашли длинный палиндром, то палиндромы внутри его правой половины зеркально повторяют палиндромы из левой. Алгоритм Манакера использует эту симметрию и не расширяется заново там, где ответ уже известен. Итог — по времени.
Подробный разбор с кодом и визуализацией — в отдельной статье Алгоритм Манакера. Здесь важно другое: что говорить на собеседовании.
- Для LeetCode 5 при линейный алгоритм не нужен. Интервьюер почти всегда ждёт расширение от центра.
- Хороший ход — после написанного решения сказать: «Существует алгоритм Манакера за , он переиспользует симметрию уже найденных палиндромов». Это показывает кругозор и не тратит время.
- Писать Манакера по памяти стоит, только если об этом прямо попросят. Код короткий, но в нём легко ошибиться с индексами, а на интервью ошибка в «продвинутом» решении хуже, чем чистое .
Если хочется узнать, как хранить сразу все различные палиндромы строки, — для этого есть палиндромное дерево. На обычных собеседованиях оно не встречается.
Типичная ловушка: развернуть строку и найти общую подстроку
Кажется логичным: палиндром совпадает со своим разворотом, значит, ответ — самая длинная общая подстрока 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
Время , память . Здесь асимптотику не улучшить перечислением: в строке "aaa…a" палиндромных подстрок , и если считать их по одной, меньше квадрата не выйдет. Манакер решает и эту задачу за — он сразу знает радиус каждого центра и складывает радиусы, не перебирая палиндромы поштучно.
Через ДП
Та же таблица, что и в задаче 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 уже посчитана — поэтому порядок корректный. Время и память — .
Обе задачи удобно решать в паре: если на интервью дали одну, вторую часто спрашивают как follow-up — «а теперь посчитайте их все».
Родственные задачи
Таблица dp[i][j] из решения 2 кажется проигрышной для задачи 5, но она пригождается там, где нужно много раз спрашивать «палиндром ли s[i..j]». Классический пример — LeetCode 131 Palindrome Partitioning: разбить строку на палиндромы всеми способами. Это бэктрекинг, и без предподсчёта каждая проверка куска стоит . С таблицей — :
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 — дописать символы в начало, чтобы получился палиндром. Нужен самый длинный палиндромный префикс, и здесь уже мало: решают через префикс-функцию, Z-функцию или Манакера.
Если вы поняли расширение от центра и таблицу dp[i][j], все эти задачи сводятся к знакомым кирпичикам.
Типичные ошибки
- Забыли чётные палиндромы. Расширяются только от символов, и
"cbbd"даёт"c"вместо"bb". Лечится вторым вызовомexpand(center, center + 1). - Ошибка на единицу в длине. После цикла
leftиrightуже указывают за пределы палиндрома. Длина —right - left - 1, а неright - left + 1. - Неправильный порядок обхода в ДП. Внешний цикл по
iот0кn - 1обращается к ещё не посчитанной строкеi + 1. Нужен обход по длине или поiс конца. - Подпоследовательность вместо подстроки. Если в формулировке «subsequence» — это LeetCode 516, там переход
dp[i][j] = max(dp[i+1][j], dp[i][j-1])при несовпадении краёв. - Срезы в цикле. В Python проверка
s[i:j] == s[i:j][::-1]внутри двойного цикла — это скрытый третий множитель . В переборе это ожидаемо, но в «оптимальном» решении срезов внутри циклов быть не должно. - Целочисленное деление в JavaScript.
(len - 1) / 2безMath.floorдаёт дробный индекс.
Как это выглядит на собеседовании
Задача популярна: она входит в большинство известных подборок вроде Blind 75 и NeetCode 150 и встречается на интервью в крупных компаниях. Хороший ход разговора обычно такой:
- Уточнить условие — подстрока или подпоследовательность, любой ли ответ подходит при равной длине, что вернуть для строки из одного символа.
- Назвать перебор за и сразу объяснить, где в нём повторяющаяся работа.
- Предложить идею центра: «У каждого палиндрома есть центр, их , от каждого расширяемся». Можно упомянуть ДП как альтернативу с памятью.
- Написать расширение от центра — 15 строк кода.
- Прогнать на примерах
"babad","cbbd","a","aaaa"— последний проверяет чётный случай и худшую сложность. - Назвать сложность / и упомянуть Манакера за .
Если вы только начинаете готовиться к задачам на строки, начните с Valid Palindrome — там та же проверка двумя указателями, но снаружи внутрь. Общий обзор строковых задач — в статье задачи на строки на собеседовании, а сама техника встречных указателей подробно разобрана в статье про два указателя.