516. Longest Palindromic Subsequence

Edited by Charles

Medium · Python · Dynamic Programming

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given a string s, return the length of the longest palindromic subsequence.

A subsequence does not need to be contiguous, but the relative order of the selected characters must remain unchanged.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

Given a string s, return the length of the longest palindromic subsequence.

A subsequence does not need to be contiguous, but the relative order of the selected characters must remain unchanged.

For example:

s = "bbbab"

One longest palindromic subsequence is:

"bbbb"

Therefore, the answer is 4.

The key observation is that when considering a substring s[i:j+1], the result depends on whether the two boundary characters s[i] and s[j] are equal.

Dynamic Programming

State Definition

Let

dp[i][j]

denote:

The length of the longest palindromic subsequence inside the substring s[i:j+1].

The interval is inclusive on both sides:

[i, j]

So dp[i][j] considers every possible subsequence inside this range.

Initialization

When

i == j

the substring contains only one character.

A single character is always a palindrome of length 1.

Therefore:

dp[i][i] = 1

All other states can initially remain 0.

State Transition

There are two cases.

Case 1: s[i] == s[j]

If the two boundary characters are equal, they can both be added to the longest palindromic subsequence inside the interval:

[i + 1, j - 1]

Therefore:

dp[i][j] = dp[i + 1][j - 1] + 2

For example:

s[i:j+1] = "cabac"

Since:

s[i] == s[j] == 'c'

we only need to know the longest palindromic subsequence inside:

"aba"

and then add the two 'c' characters.

Case 2: s[i] != s[j]

If the two boundary characters are different, they cannot both be included as matching ends of the same palindrome.

We consider two possibilities:

• Ignore s[i]
• Ignore s[j]

If we ignore s[i], the result is:

dp[i + 1][j]

If we ignore s[j], the result is:

dp[i][j - 1]

Take the larger value:

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

Transition Equation

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])

Traversal Order

The transition depends on:

dp[i + 1][j - 1]
dp[i + 1][j]
dp[i][j - 1]

Therefore, before computing dp[i][j]:

• the next row i + 1 must already be computed;
• the value to the left dp[i][j - 1] must already be computed.

So i must be traversed from bottom to top:

for i in range(len(s) - 1, -1, -1):

and j should move from left to right:

for j in range(i + 1, len(s)):

Traversal order:

i: right to left / bottom to top
j: left to right

Final Answer

The state:

dp[0][len(s) - 1]

represents the longest palindromic subsequence inside the entire string.

Therefore, the final answer is:

dp[0][-1]

Example

s = "cbbd"

Initialization:

dp[0][0] = 1   # "c"
dp[1][1] = 1   # "b"
dp[2][2] = 1   # "b"
dp[3][3] = 1   # "d"

Compare s[2] and s[3]

'b' != 'd'

Therefore:

dp[2][3] = max(dp[3][3], dp[2][2])
         = 1

Compare s[1] and s[2]

'b' == 'b'

Therefore:

dp[1][2] = dp[2][1] + 2
         = 2

The palindrome is:

"bb"

Compare s[1] and s[3]

'b' != 'd'

Therefore:

dp[1][3] = max(dp[2][3], dp[1][2])
         = 2

Compare s[0] and s[3]

'c' != 'd'

Therefore:

dp[0][3] = max(dp[1][3], dp[0][2])
         = 2

Final answer:

2

Complexity Analysis

Time Complexity

O(n²)

We compute every valid interval [i, j].

Space Complexity

O(n²)

A 2D DP table is used.

Summary

State Definition

dp[i][j] = length of the longest palindromic subsequence inside s[i:j+1]

Initialization

dp[i][i] = 1

State Transition

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])

Traversal Order

i: from right to left
j: from i + 1 to right

Final Answer

dp[0][-1]

Common Mistakes

1. Do not confuse palindromic subsequence with palindromic substring.

Substring   -> must be contiguous
Subsequence -> does not need to be contiguous

1. When:

s[i] == s[j]

both boundary characters can be included:

dp[i][j] = dp[i + 1][j - 1] + 2

1. When:

s[i] != s[j]

do not reset the state to 0.

Instead, discard one boundary and take the better result:

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

1. The traversal order is important because dp[i][j] depends on states from the next row. Therefore, i must be traversed from right to left.
2. Every single character is a palindrome of length 1, so the diagonal must be initialized as:

dp[i][i] = 1

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 12, 2026

Python solution

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        l = len(s)
        dp = [[0] * l for _ in range(l)]
        for i in range(l):
            dp[i][i] = 1

        for i in range(l - 1, -1, -1):
            for j in range(i + 1, l):
                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[0][-1]

---

Back to Day 40 Dynamic Programming XIII · All Algorithm notes