Introduction

The longest palindromic subsequence problem asks for the longest sequence of characters that reads the same forward and backward, without requiring the characters to stay contiguous. The standard solution uses dynamic programming because the problem has overlapping subproblems and a clean recurrence.

Subsequence Versus Substring

A subsequence can skip characters, while a substring must stay contiguous. For example, in bbbab, the longest palindromic subsequence is bbbb, even though those four characters are not all adjacent.

That distinction is why algorithms for longest palindromic substring do not directly solve longest palindromic subsequence.

Dynamic Programming Recurrence

Let dp[i][j] be the length of the longest palindromic subsequence in the slice from index i to index j.

The recurrence is:

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

The base case is that every single character is a palindrome of length 1, so dp[i][i] = 1.

Bottom-Up Implementation

A bottom-up table is usually the clearest implementation.

1def longest_palindromic_subsequence_length(s: str) -> int:
2    n = len(s)
3    if n == 0:
4        return 0
5
6    dp = [[0] * n for _ in range(n)]
7
8    for i in range(n):
9        dp[i][i] = 1
10
11    for length in range(2, n + 1):
12        for i in range(n - length + 1):
13            j = i + length - 1
14            if s[i] == s[j]:
15                if length == 2:
16                    dp[i][j] = 2
17                else:
18                    dp[i][j] = dp[i + 1][j - 1] + 2
19            else:
20                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
21
22    return dp[0][n - 1]
23
24print(longest_palindromic_subsequence_length("bbbab"))

This runs in O(n^2) time and uses O(n^2) space.

Reconstruct The Actual Subsequence

Sometimes the length is not enough. You may also want the subsequence itself. One way is to walk backward through the DP table.

1def longest_palindromic_subsequence(s: str) -> str:
2    n = len(s)
3    if n == 0:
4        return ""
5
6    dp = [[0] * n for _ in range(n)]
7    for i in range(n):
8        dp[i][i] = 1
9
10    for length in range(2, n + 1):
11        for i in range(n - length + 1):
12            j = i + length - 1
13            if s[i] == s[j]:
14                dp[i][j] = 2 if length == 2 else dp[i + 1][j - 1] + 2
15            else:
16                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
17
18    left = []
19    right = []
20    i, j = 0, n - 1
21
22    while i <= j:
23        if i == j:
24            left.append(s[i])
25            break
26        if s[i] == s[j]:
27            left.append(s[i])
28            right.append(s[j])
29            i += 1
30            j -= 1
31        elif dp[i + 1][j] >= dp[i][j - 1]:
32            i += 1
33        else:
34            j -= 1
35
36    return "".join(left + right[::-1])
37
38print(longest_palindromic_subsequence("bbbab"))

The reconstruction step follows the same logic used to fill the table.

Why The Recurrence Works

If the two end characters match, any best subsequence inside the smaller range can be extended by those two matching characters. If the ends do not match, the optimal subsequence must exclude one end or the other, so the answer is the best of those two smaller ranges.

This is exactly the kind of local choice dynamic programming handles well.

Common Pitfalls

A common mistake is confusing the problem with longest palindromic substring. Substring algorithms depend on contiguity, but subsequences can skip positions.

Another mistake is filling the DP table in the wrong order. Since dp[i][j] depends on smaller ranges, the table must be built from short slices to long slices.

It is also easy to forget the length == 2 case when two equal adjacent characters appear. Without that case, the lookup to the inner subproblem can be awkward.

Summary

• Longest palindromic subsequence is a dynamic programming problem, not a greedy one.
• Use dp[i][j] to store the best answer for each substring range.
• The standard recurrence gives an O(n^2) time solution.
• You can reconstruct the actual subsequence by walking the finished table.
• Do not confuse subsequences with substrings because the algorithms are different.