LeetCode 516: Longest Palindromic Subsequence

Problem Restatement

We are given a string s.

We need to return the length of the longest subsequence of s that is also a palindrome.

A subsequence is made by deleting zero or more characters without changing the order of the remaining characters.

A palindrome reads the same forward and backward.

The official problem asks for the length of the longest palindromic subsequence in s. The constraints are 1 <= s.length <= 1000, and s contains only lowercase English letters.

Input and Output

Function shape:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        ...

Examples

Example 1:

s = "bbbab"

One longest palindromic subsequence is:

bbbb

Its length is:

4

So the answer is:

4

Example 2:

s = "cbbd"

One longest palindromic subsequence is:

bb

Its length is:

2

So the answer is:

2

First Thought: Try All Subsequences

A direct idea is to generate every subsequence and check whether it is a palindrome.

For a string of length n, each character can either be kept or deleted.

So there are:

2^n

possible subsequences.

This is too slow for n up to 1000.

Problem With Brute Force

The brute force method repeats the same work many times.

For example, when deciding whether to use the first or last character, both choices lead to smaller substring problems.

The same substring ranges appear again and again.

This suggests dynamic programming over intervals.

Key Insight

Let:

dp[i][j]

mean:

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

Now compare the two ends of the substring.

If:

s[i] == s[j]

then these two equal characters can be used as the outer characters of a palindrome.

So:

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

If:

s[i] != s[j]

then the best palindrome cannot use both ends together.

So we take the better result from dropping one side:

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

Each single character is a palindrome of length 1, so:

dp[i][i] = 1

Algorithm

Let n = len(s).

Create a 2D table:

dp = [[0] * n for _ in range(n)]

Initialize:

dp[i][i] = 1

Then fill the table by increasing substring length.

For every substring s[i:j+1]:

1. If s[i] == s[j], use both ends.
2. Otherwise, drop the left end or the right end and take the better result.

Return:

dp[0][n - 1]

Correctness

The table entry dp[i][j] represents the longest palindromic subsequence inside the substring from index i to index j.

For a substring of length 1, the answer is 1, since one character is always a palindrome.

For longer substrings, there are two cases.

If s[i] == s[j], any longest palindromic subsequence inside s[i + 1:j] can be extended by placing s[i] and s[j] around it. This gives a palindrome of length dp[i + 1][j - 1] + 2.

If s[i] != s[j], a palindrome cannot use both endpoints as matching outer characters. So an optimal answer must be contained either in s[i + 1:j + 1] or in s[i:j]. The algorithm takes the maximum of these two values.

Because the table is filled from shorter substrings to longer substrings, every needed subproblem is already computed before it is used.

Therefore dp[0][n - 1] is the length of the longest palindromic subsequence of the full string.

Complexity

Implementation

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

        for i in range(n):
            dp[i][i] = 1

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                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][n - 1]

Code Explanation

Create the DP table:

dp = [[0] * n for _ in range(n)]

Set all one-character substrings:

for i in range(n):
    dp[i][i] = 1

Then process substrings by length:

for length in range(2, n + 1):

For each substring, compute the end index:

j = i + length - 1

If the endpoints match:

if s[i] == s[j]:
    dp[i][j] = dp[i + 1][j - 1] + 2

Otherwise, drop one endpoint:

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

The final answer is the full interval:

return dp[0][n - 1]

Testing

def test_longest_palindrome_subseq():
    s = Solution()

    assert s.longestPalindromeSubseq("bbbab") == 4
    assert s.longestPalindromeSubseq("cbbd") == 2
    assert s.longestPalindromeSubseq("a") == 1
    assert s.longestPalindromeSubseq("aaaa") == 4
    assert s.longestPalindromeSubseq("abcde") == 1
    assert s.longestPalindromeSubseq("agbdba") == 5

    print("all tests passed")

Test meaning: