516. Longest Palindromic Subsequence

516

MediumTwo-Dimensional Dynamic ProgrammingInterval dynamic programmingInterval DP matching endpoints

Longest Palindromic Subsequence

Given a string s, return the length of the longest palindromic subsequence of s. A subsequence is formed by deleting zero or more characters without reordering the rest, and it is a palindrome if it reads the same forwards and backwards.

Open official problem prompt ↗

In plain English

Compute the length of the longest subsequence of s that is a palindrome, without needing to construct it.

Picture it like this

Imagine matching the outermost bookends on a shelf: if the two end books are identical you keep both and recurse on the shelf between them; if not, you set one end aside and try the rest.

Example

Input: s = "bbbab"
Output: 4
Why: The subsequence "bbbb" (dropping the 'a') is a palindrome of length 4.

Constraints

1 <= s.length <= 1000s consists only of lowercase English letters

Pattern lesson

See the pattern, then code

Interval DP matching endpoints

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. For a range [i, j], if the end characters match they can both wrap around whatever is optimal inside [i+1, j-1], adding 2; if they differ, at least one end cannot be used, so take the better of dropping either end.

New words, made simpleKnow these before the algorithm

Subsequence: Characters kept in order after deleting some, not necessarily contiguous.
Palindrome: A sequence identical when reversed.
Endpoint match: The DP transition that pairs s[i] with s[j] to extend an inner palindrome by two.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate subsequences

Exponential; unusable past ~20 characters.

Generate all subsequences and test each for palindromeness.

Time O(2^n * n)Space O(n)

LCS with reverse

Correct and elegant but relies on a non-obvious equivalence; the direct DP is clearer.

Longest common subsequence of s and its reverse equals the answer.

Time O(n^2)Space O(n^2)

Best choiceDirect interval DP

Direct, provably correct, and the standard interview answer.

dp[i][j] built from endpoint matching over ranges.

Time O(n^2)Space O(n^2)

The rule we keep true

Invariant

dp[i][j] always holds the length of the longest palindromic subsequence contained entirely within s[i..j].

Why this is correct

Reasoning

Any palindromic subsequence of s[i..j] either uses both endpoints (only possible when they are equal, contributing 2 plus the best inner solution) or omits at least one endpoint (covered by dropping the left or right character). These cases are exhaustive, so the max over them is optimal.

The algorithm in three movesSay these aloud before coding

1Let dp[i][j] be the longest palindromic subsequence within s[i..j]

s[0]==s[4]=='b' -> dp[0][4]=dp[1][3]+2

2Base case: every single character is a palindrome of length 1

dp[1][3] over "bba" = 2

3If s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2

dp[0][4] = 2 + 2 = 4

4Otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1])

5Iterate i downward and j upward so inner ranges are ready; return dp[0][n-1]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads = "bbbab"

2 · AskSingle chars?

3 · Update statedp[i][i] = 1 for all i

4 · ResultDiagonal set to 1

Key takeaway

Matching endpoints 'b' and 'b' let the inner range contribute plus two.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Setup and base
Iterate i from the end backward so dp[i+1][...] is ready; each single char is length 1.
2
Lines 6-9Matching ends
Equal endpoints wrap the inner best solution and add two.
3
Lines 10-11Mismatched ends
Drop whichever endpoint helps less and take the better remaining range.
4
Lines 12Answer
dp[0][n-1] covers the whole string.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single character returns 1
Already-palindrome string returns its full length
No repeats (e.g. "abcde") returns 1

Common beginner mistakes

Iterating i in increasing order, which reads uncomputed dp[i+1][j-1]
Confusing subsequence with substring (contiguity is not required here)
Forgetting the +2 covers both matched endpoints, not +1

Check your understanding

When s[i] != s[j], why can we ignore the combination that uses both endpoints?

Longest Palindromic Subsequence

Longest Palindromic Subsequence

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming