Palindromic Subsequence DP

Interval DP over a string: dp[i][j] describes the piece from i to j, and matching end characters let you grow a palindrome from the inside out.

Overview

Two words that look alike

A palindrome reads the same forward and backward: 'racecar', 'abba', or a single character. Problems ask about palindromes inside a longer string, and the first thing to settle is which kind.

Characters — Next to each other — In order, gaps allowed
Example in 'bbbab' — 'bbb' is a palindromic substring — 'bbbb' is a palindromic subsequence
Count of pieces — About n² of them — About 2ⁿ of them
What DP stores — Is s[i..j] a palindrome? (yes or no) — The best answer for s[i..j] (a number)

Both kinds use the same state, dp[i][j] for the piece of the string from index i to index j. That makes them interval DP: a longer piece is answered from shorter pieces inside it.

The longest palindromic subsequence

Let dp[i][j] be the length of the longest palindromic subsequence (LPS) inside s[i..j]. Look at the two end characters.

The base cases are one character (length 1) and the empty piece (length 0, when i > j). Here is the full table for 'bbbab'. Only cells with i ≤ j exist; the answer is the top right cell.

0 (b) — 1 — 2 — 3 — 3 — 4
1 (b) — 1 — 2 — 2 — 3
2 (b) — 1 — 1 — 3
3 (a) — 1 — 1
4 (b) — 1

A few cells, in the order they are filled (by piece length).

s[2..3] = 'ba' — b, a — drop an end — dp[3][3] = 1, dp[2][2] = 1 — 1
s[3..4] = 'ab' — a, b — drop an end — dp[4][4] = 1, dp[3][3] = 1 — 1
s[2..4] = 'bab' — b, b — wrap — dp[3][3] = 1 — 3
s[1..4] = 'bbab' — b, b — wrap — dp[2][3] = 1 — 3
s[0..4] = 'bbbab' — b, b — wrap — dp[1][3] = 2 — 4

The answer 4 is 'bbbb'. Every cell costs O(1) and there are about n²/2 cells, so the time is O(n²). Row i reads only row i + 1 and its own row, so two rows are enough: O(n) space.

The fill order

A cell needs the cells inside it. Two orders work.

By piece length — length 1, 2, 3, ... then every i — Shorter pieces are always done first
i downward, j upward — i from n − 1 to 0, j from i + 1 to n − 1 — Row i + 1 is complete before row i starts, and dp[i][j-1] was just filled

Looping i upward from 0 fails: dp[0][j] needs dp[1][j-1], which does not exist yet.

Substrings: a yes-or-no table, or expand from the center

For substrings, dp[i][j] is true when s[i..j] is a palindrome. That holds when s[i] == s[j] and the inside is a palindrome (or the inside has at most one character). The table takes O(n²) time and space and answers both 'longest palindromic substring' and 'count palindromic substrings'.

The same two problems have a simpler O(n²) time, O(1) space solution: expand around the center. A palindrome has a center, either a character (odd length) or the gap between two characters (even length). There are 2n − 1 centers. From each, move outward while the two characters match.

a (index 0) — 'a' — stops at the edge — 1
gap between a and b — empty — a ≠ b, stops — 0
b (index 1) — 'b' — a ≠ b, stops — 1
gap between b and b — 'bb' — 'abba', then the edge — 2
b (index 2) — 'b' — b ≠ a, stops — 1
gap between b and a — empty — b ≠ a, stops — 0
a (index 3) — 'a' — stops at the edge — 1

Total: 6 palindromic substrings, and the longest is 'abba'. Manacher's algorithm does the same in O(n), but it is rarely needed; name it and move on.

Problems that reduce to LPS

Once you have LPS, several questions are one subtraction away. The characters outside the longest palindromic subsequence are the ones you must delete, or the ones you must mirror with an insertion.

Fewest deletions to make a palindrome — n − LPS(s) — 5 − 4 = 1 (delete the 'a')
Fewest insertions to make a palindrome — n − LPS(s) — 1 (insert an 'a')
LPS via a known algorithm — LCS(s, reverse of s) — LCS('bbbab', 'babbb') = 4

Partitioning: two DP tables in a row

'Palindrome Partitioning II' asks for the fewest cuts that split s into palindromic pieces. It combines a substring table with a 1D DP.

For 'aab': pal says 'aa' and 'b' are palindromes, so cuts[2] = cuts[1] + 1 = 0 + 1 = 1. One cut, into 'aa' and 'b'.

What you will be able to do

Tell substring from subsequence in the first minute and pick the right table.
Write the LPS recurrence and fill a 5 by 5 table by hand without a mistake.
Choose a fill order that never reads an empty cell.
Solve the deletion, insertion and LCS variants by reduction to LPS.
Explain why palindrome partitioning needs a precomputed table to stay O(n²).

When to use it

The question asks for the longest palindromic subsequence or substring
The question asks how many palindromic substrings or subsequences a string has
The question asks for the fewest deletions or insertions that make a string a palindrome
The question asks to split a string into palindromic pieces with the fewest cuts
The best answer for a piece s[i..j] is built from the pieces just inside it

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio