Medium Problemspalindromestringinterval

Longest Palindromic Subsequence

Given a string, find the length of the longest subsequence of its characters that reads the same forwards and backwards. The chosen characters must keep their original order but need not be adjacent.

Do this lesson first: longest common subsequence

Example input

s = "bbabcb"

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] = 2 + dp[i + 1][j - 1] if s[i] = s[j] (just 2 when j = i + 1), otherwise max(dp[i + 1][j], dp[i][j - 1])

Ask what happens to the two end characters, s[i] and s[j]. This is the LCS decision, and its derivation lives in the LCS lesson at /courses/dynamic-programming/longest-common-subsequence; only the setting changes, the two ends of one stretch instead of the last characters of two strings. If the ends match, using them as the outer pair is never worse: a best palindrome that skipped one of them could swap its own outer pair for s[i] and s[j] without getting shorter. So wrap the best palindrome strictly inside, dp[i][j] = 2 + dp[i + 1][j - 1], which is LCS's diagonal step. If the ends differ, no palindrome in the stretch can use both, because its first and last characters would have to be s[i] and s[j]. So at least one end is out: drop the left (dp[i + 1][j]) or drop the right (dp[i][j - 1]) and keep the longer, which is LCS's max of up and left. It is a max because one dropped end is enough and you want the better of the two, and nothing is added because no character joined the palindrome.

dp[i][i] = 1 on the diagonal: a single character is a palindrome. A length-2 stretch with matching ends, like 'bb' at dp[0][1], is set to 2 without reading anything, because its inside, dp[i + 1][i], would sit below the diagonal and is not a stretch at all. Every other cell reads only shorter stretches inside its own: the one below it (left end dropped), the one to its left (right end dropped), or the one diagonally below-left (both ends kept). Filling by length, every length-2 stretch, then every length-3 stretch, and so on, guarantees each of those is final before it is read. On the grid that is a sweep along the diagonals, from the main one out to the top-right corner.

Tabulation over all n(n + 1) / 2 stretches with constant work at each, so O(n²) time; at 6 characters that is 21 cells, 6 bases and 15 computes. Top-down memoization from dp[0][n - 1] also works and skips any stretch no chain of choices reaches, at the price of recursion as deep as the string. A cell reads only its own row and the row below it, so if i runs from n - 1 down to 0 with j rising, two rows of length n are enough and space falls to O(n). That is the same dependency order as filling by length, cut along rows instead of diagonals.

Time O(n²)Space O(n²), reducible to O(n)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[i][i] = 1 on the diagonal: a single character is a palindrome. A length-2 stretch with matching ends, like 'bb' at dp[0][1], is set to 2 without reading anything, because its inside, dp[i + 1][i], would sit below the diagonal and is not a stretch at all. Every other cell reads only shorter stretches inside its own: the one below it (left end dropped), the one to its left (right end dropped), or the one diagonally below-left (both ends kept). Filling by length, every length-2 stretch, then every length-3 stretch, and so on, guarantees each of those is final before it is read. On the grid that is a sweep along the diagonals, from the main one out to the top-right corner.

Rows ↓
Cols →

0 b

1 b

2 a

3 b

4 c

5 b

0 b

1

2

3

5

1 b

·

1

3

2 a

·

1

3

3 b

·

1

3

4 c

·

1

5 b

·

1

Rows ↓row i: where the stretch of the string starts

Cols →column j: where it ends, so the cell is the longest palindromic subsequence of s[i..j]

longest-palindromic-subsequence.ts

1function longestPalindromeSubseq(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let i = 0; i < n; i++) dp[i][i] = 1;
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 dp[i][j] = s[i] === s[j]
9 ? (len === 2 ? 2 : 2 + dp[i + 1][j - 1])
10 : Math.max(dp[i + 1][j], dp[i][j - 1]);
11 }
12 }
13 return dp[0][n - 1];
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-palindromic-subsequence.ts

1function longestPalindromeSubseq(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
4 for (let i = 0; i < n; i++) dp[i][i] = 1;
5 for (let len = 2; len <= n; len++) {
6 for (let i = 0; i + len - 1 < n; i++) {
7 const j = i + len - 1;
8 dp[i][j] = s[i] === s[j]
9 ? (len === 2 ? 2 : 2 + dp[i + 1][j - 1])
10 : Math.max(dp[i + 1][j], dp[i][j - 1]);
11 }
12 }
13 return dp[0][n - 1];
14}

Where people go wrong

Filling the triangle row by row from the top, i rising and then j rising, the way a grid fills. dp[0][j] then reads dp[1][...] before row 1 has been computed, and in a zero-filled array that read quietly returns 0 instead of failing. Measured on this page's string, that loop returns 2 at every slider size, which is right only at 2 and 3 characters; at 6 it says 2 where the answer is 5. Fill by length, or run i downwards from n - 1. The other classic slip is answering the substring question: the longest run of ADJACENT characters in 'bbabcb' that is a palindrome is 'bab' or 'bcb', length 3, not 5.

Find the fewest deletions that leave a palindrome.
The table does not change at all; the answer becomes n - dp[0][n - 1]: keep a longest palindromic subsequence and delete everything else. On 'bbabcb' that is 6 - 5 = 1, the 'c'. minimum-insertions-for-palindrome asks the mirror question and reaches the same n minus this number from a table of its own.
Compute it as the longest common subsequence of s and s reversed.
The state changes to a pair of prefixes, i characters of s against j characters of its reverse, an (n + 1) by (n + 1) rectangle filled row by row with exactly the recurrence of the LCS lesson (/courses/dynamic-programming/longest-common-subsequence); nothing new is derived. The length always agrees: 'bbabcb' against 'bcbabb' has an LCS of 5. What does not carry over is the string itself. An LCS of 'bacba' and its reverse 'abcab' can come out as 'acb' or 'bca', the right length, 3, and neither one a palindrome. Rebuild from this triangle when you need the palindrome and not just its length.
Return the palindrome itself, not its length.
The table is unchanged; walk it back from dp[0][n - 1]. Matching ends: keep both and step to dp[i + 1][j - 1]. Differing ends: step to whichever of the two neighbours holds the larger value. At 6 characters the walk visits dp[0][5], dp[1][4], dp[1][3] and dp[2][2] and spells 'bbabb'.
Require the palindrome to be contiguous: the longest palindromic substring.
Dropping an end is no longer allowed, so the max disappears. A stretch either is a palindrome or is not: its ends match AND its inside is a palindrome. The cell becomes a yes-or-no flag, the table palindromic-substring-count builds, and the answer is the longest stretch flagged yes. Same triangle and same fill by length; on 'bbabcb' the answer drops from 5 to 3.

Partition Problem Longest Common Increasing Subsequence