Наибольшая палиндромная подпоследовательность: ДП за O(n²) и отличие от подстроки

Longest Palindromic Subsequence (LeetCode 516): чем подпоследовательность отличается от подстроки, ДП по отрезкам, память O(n), восстановление ответа и задачи-родственники 1312 и 1216.

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

Коротко

ПараметрЗначение
ЗадачаLeetCode 516: длина самой длинной подпоследовательности-палиндрома
Состояниеdp[i][j] — ответ для s[i..j]
Переходs[i] == s[j] → dp[i+1][j-1] + 2, иначе max(dp[i+1][j], dp[i][j-1])
СложностьO(n2)O(n^2) по времени, O(n)O(n) по памяти в оптимизированной версии
Главная ловушкаперепутать с подстрокой: там нужна непрерывность, здесь — нет

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

Подстрока или подпоследовательность

Это две разные задачи, и на собеседовании их путают чаще, чем кажется.

  • Подстрока — непрерывный кусок: в character подстроки char, act, rac. Самая длинная подстрока-палиндром — ara, длина 3. Это LeetCode 5, разобранный в статье про наибольшую палиндромную подстроку.
  • Подпоследовательность — любые символы в исходном порядке, пропуски разрешены. В character можно взять c_ar_ac___ и получить carac, длина 5. Это LeetCode 516.
СтрокаПодстрока-палиндромПодпоследовательность-палиндром
bbbabbbb (3)bbbb (4)
characterara (3)carac (5)
agbdbabdb (3)abdba (5)
abcdecaa (1)aceca (5)
zzazzzzazz (5)zzazz (5)

Подпоследовательность-палиндром всегда не короче подстроки, ведь любая подстрока — тоже подпоследовательность. Разница бывает огромной: в abcdeca нет ни одной подстроки-палиндрома длиннее одного символа, а подпоследовательность длины 5 есть.

Отсюда практическое следствие: для подстрок достаточно перебрать центры, потому что палиндром «растёт» из центра без разрывов. Для подпоследовательностей центр ничего не даёт — между выбранными символами могут быть дыры любой длины.

Перебор и почему он не годится

У строки длины n ровно 2n2^n подпоследовательностей. Перебрать их все и проверить каждую на палиндромность — O(n⋅2n)O(n \cdot 2^n). Для n = 1000 (ограничение в LeetCode 516) это за гранью разумного. Как устроен такой перебор, разобрано в статье про подмножества, но здесь он нужен только как отправная точка.

Рекурсия по краям

Ключевой вопрос: что делать с первым и последним символом отрезка s[i..j]?

  1. Они равны. Тогда их выгодно взять оба: они станут внешней парой палиндрома, а внутри останется задача для s[i+1..j-1]. Ответ — 2 + solve(i + 1, j - 1).
  2. Они разные. Тогда оба одновременно в палиндром войти не могут (они стояли бы на симметричных местах). Значит, хотя бы один лишний: max(solve(i + 1, j), solve(i, j - 1)).

Почему в первом случае не нужно рассматривать вариант «выбросить одного из равных»? Пусть оптимальный палиндром внутри s[i..j] не использует s[i]. Его первый символ — какой-то s[p], последний — s[q], причём s[p] == s[q]. Заменим s[p] на s[i], а s[q] на s[j] — длина та же, палиндром сохранился. Значит, всегда есть оптимальный ответ, который берёт оба края.

Базовые случаи: пустой отрезок даёт 0, один символ — 1.

from functools import lru_cache def lps_memo(s: str) -> int: @lru_cache(maxsize=None) def solve(i: int, j: int) -> int: if i > j: return 0 if i == j: return 1 if s[i] == s[j]: return solve(i + 1, j - 1) + 2 return max(solve(i + 1, j), solve(i, j - 1)) return solve(0, len(s) - 1) print(lps_memo('bbbab')) # 4 print(lps_memo('cbbd')) # 2

Без lru_cache это экспонента: при различных краях рекурсия ветвится на два. С кэшем — всего n2/2n^2/2 различных пар (i, j), каждая считается за O(1)O(1). Подробнее о приёме — в статье про мемоизацию.

Для n = 1000 рекурсия упрётся в лимит глубины Python (по умолчанию 1000), поэтому дальше — итеративная версия.

Таблица снизу вверх

dp[i][j] читает dp[i+1][...] (строку ниже) и dp[i][j-1] (ячейку левее). Значит, строки заполняем снизу вверх, а внутри строки — слева направо.

def lps_table(s: str) -> list[list[int]]: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp print(lps_table('agbdba')[0][-1]) # 5

Для j = i + 1 и равных символов код читает dp[i+1][i] — это ячейка ниже диагонали, она равна 0, и ответ получается 2. Отдельно этот случай обрабатывать не нужно, но стоит проговорить вслух на собеседовании.

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

Строка agbdba, индексы 0–5. Таблица после заполнения (строка — i, столбец — j):

agbdba
a111135
g11133
b1133
d111
b11
a1

Несколько ключевых ячеек:

  • dp[2][4] — отрезок bdb. Края равны: dp[3][3] + 2 = 3.
  • dp[1][4] — gbdb. Края g и b разные: max(dp[2][4], dp[1][3]) = max(3, 1) = 3.
  • dp[1][5] — gbdba. Края разные: max(dp[2][5], dp[1][4]) = 3.
  • dp[0][5] — вся строка. Края a и a равны: dp[1][4] + 2 = 5.

Ответ 5 — палиндром abdba.

Память O(n)

Строке i нужна только строка i + 1. Храним две строки — prev (это dp[i+1]) и cur (dp[i]):

def lps_linear(s: str) -> int: n = len(s) prev = [0] * n # строка dp[i + 1] for i in range(n - 1, -1, -1): cur = [0] * n # строка dp[i] cur[i] = 1 for j in range(i + 1, n): if s[i] == s[j]: cur[j] = prev[j - 1] + 2 else: cur[j] = max(prev[j], cur[j - 1]) prev = cur return prev[n - 1] if n else 0 print(lps_linear('character')) # 5

Для n = 1000 это миллион простых операций; в CPython — порядка десятой доли секунды. Можно ужать и до одного массива, сохраняя «диагональное» значение во временной переменной, но выигрыш копеечный, а читаемость падает.

То же на JavaScript:

function longestPalindromeSubseq(s) { const n = s.length let prev = new Array(n).fill(0) for (let i = n - 1; i >= 0; i--) { const cur = new Array(n).fill(0) cur[i] = 1 for (let j = i + 1; j < n; j++) { cur[j] = s[i] === s[j] ? prev[j - 1] + 2 : Math.max(prev[j], cur[j - 1]) } prev = cur } return n ? prev[n - 1] : 0 } console.log(longestPalindromeSubseq('bbbab')) // 4

Восстановить сам палиндром

Длина — хорошо, но часто просят и строку. Для этого нужна полная таблица: идём от (0, n-1) и повторяем решения, которые принимала динамика.

def restore(s: str) -> str: dp = lps_table(s) left, middle = [], '' i, j = 0, len(s) - 1 while i <= j: if i == j: middle = s[i] # центральный символ нечётного палиндрома break if s[i] == s[j]: left.append(s[i]) i += 1 j -= 1 elif dp[i + 1][j] >= dp[i][j - 1]: i += 1 else: j -= 1 return ''.join(left) + middle + ''.join(reversed(left)) print(restore('character')) # carac print(restore('agbdba')) # abdba

Собираем только левую половину, правая — её зеркало. Я прогнал эту функцию на двух тысячах случайных строк: результат всегда палиндром, всегда подпоследовательность исходной строки и всегда нужной длины.

Связь с LCS

Известный трюк: длина наибольшей палиндромной подпоследовательности строки s равна длине наибольшей общей подпоследовательности s и s[::-1].

Почему это верно: палиндром, который сидит в s как подпоследовательность, в развёрнутом виде сидит и в s[::-1] — а он совпадает сам с собой. Значит, LCS не меньше LPS. Обратное неравенство менее очевидно (общая подпоследовательность строки и её разворота не обязана быть палиндромом), но из любой общей подпоследовательности максимальной длины можно построить палиндром той же длины, так что числа совпадают.

На собеседовании это хороший ответ «а можно ли свести к известной задаче?». Но как основное решение отрезочная динамика удобнее: она сразу работает с одной строкой и легче восстанавливает ответ.

Важно не перенести трюк на подстроки: «общая подстрока s и s[::-1]» не даёт палиндромную подстроку. Для abacdfgdcaba общая подстрока abacd не палиндром. Это разобрано в статье про палиндромную подстроку.

Задачи на той же таблице

LPS редко спрашивают в лоб — чаще она прячется внутри другой формулировки.

1312. Minimum Insertion Steps to Make a String Palindrome. Сколько символов вставить, чтобы строка стала палиндромом? Символы, вошедшие в LPS, уже стоят парами; каждому остальному нужна «пара» — одна вставка. Ответ: len(s) - lps(s). Для mbadm — 2 (mbdadbm), для leetcode — 5.

Минимум удалений до палиндрома. Тот же ответ len(s) - lps(s): удаляем всё, что не вошло в палиндром.

1216. Valid Palindrome III. Можно ли сделать строку палиндромом, удалив не больше k символов? Проверяем len(s) - lps(s) <= k.

def min_insertions(s: str) -> int: return len(s) - lps_linear(s) def is_k_palindrome(s: str, k: int) -> bool: return len(s) - lps_linear(s) <= k print(min_insertions('mbadm')) # 2 print(min_insertions('leetcode')) # 5 print(is_k_palindrome('abcdeca', 2)) # True

Сравните с Valid Palindrome и его версией II (удалить не больше одного символа): там хватает двух указателей, потому что разрешено всего одно ветвление. При произвольном k ветвлений становится слишком много, и нужна динамика.

730. Count Different Palindromic Subsequences — уже hard: та же сетка dp[i][j], но считаются различные палиндромы, и при равных краях приходится вычитать дубликаты. Хорошая задача, чтобы проверить, что вы действительно поняли структуру, а не заучили формулу.

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

  • Решать как подстроку. Расширение от центра даст 3 для bbbab вместо 4. Если в условии слово subsequence — центр не поможет.
  • Неверный порядок обхода. for i in range(n) сверху вниз читает ещё не посчитанную строку dp[i+1]. Нужно i от n - 1 к 0 или обход по длине отрезка.
  • Забыть dp[i][i] = 1. Тогда для нечётных палиндромов теряется центральный символ, и aba даёт 2.
  • Брать max из трёх вариантов при равных краях. Это не ошибка по результату, но лишний код; обоснование, почему достаточно dp[i+1][j-1] + 2, — выше.
  • Рекурсия на n = 1000 в Python. Глубина рекурсии около n, и при стандартном лимите получите RecursionError. Либо sys.setrecursionlimit, либо итеративная таблица.

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

LeetCode 516 — задача уровня medium, её дают как проверку ДП по двум индексам. Обычный сценарий:

  1. Уточнить, подстрока или подпоследовательность. Сам вопрос — уже плюс.
  2. Рассуждение про крайние символы и рекуррентность.
  3. Мемоизация, затем таблица, затем память O(n)O(n) по запросу.
  4. Follow-up: восстановить палиндром или ответить на 1312.

Общий шаблон таких задач (отрезок, края, порядок обхода) и более тяжёлые примеры вроде Burst Balloons и перемножения цепочки матриц собраны в статье про ДП по отрезкам. Если хочется закрепить динамику на строках, следующий шаг — расстояние Левенштейна и разбиение на палиндромы.

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

Все задачи