AlgoMaster Logo

Longest Palindromic Subsequence

Last Updated: March 28, 2026

medium
5 min read

Understanding the Problem

We need to find the length of the longest subsequence of s that reads the same forwards and backwards. A subsequence doesn't have to be contiguous, so we can skip characters as long as we keep the relative order.

For example, in "bbbab", the subsequence "bbbb" (characters at indices 0, 1, 2, 4) is a palindrome of length 4. We can't do better than that, so the answer is 4.

The key observation is this: if the first and last characters of a string match, they can both be part of the palindromic subsequence, and we recurse on the substring between them. If they don't match, we try dropping either the first or the last character and take the better result. This naturally leads to a recursive structure with overlapping subproblems, which is a strong signal for dynamic programming.

Key Constraints:

  • 1 <= s.length <= 1000 --> With n up to 1000, O(n^2) gives us 1 million operations, which is comfortable. O(n^3) would mean 1 billion, which is too slow. So we need O(n^2) or better.
  • s consists only of lowercase English letters --> 26 possible characters. This limits the alphabet size but doesn't change our approach significantly.

Approach 1: Recursive Brute Force with Memoization

Intuition

Let's start from the recursive structure. Consider the substring s[i..j]. We want the longest palindromic subsequence in this range.

If s[i] == s[j], both characters can sit on opposite ends of our palindrome. We take them both and recurse on s[i+1..j-1], adding 2 to the result.

If s[i] != s[j], at least one of them can't be in the palindrome. So we try two options: skip the left character (solve s[i+1..j]) or skip the right character (solve s[i..j-1]), and take the maximum.

The base cases are simple: a single character is always a palindrome of length 1, and an empty range gives 0.

Without memoization, this recursion explores overlapping subproblems repeatedly. For example, solving s[2..5] might be needed when we drop the left from s[1..5] and also when we drop the right from s[2..6]. Memoization caches these results so each subproblem is solved only once.

Algorithm

  1. Define a recursive function solve(i, j) that returns the longest palindromic subsequence in s[i..j].
  2. Base case: if i > j, return 0. If i == j, return 1.
  3. If s[i] == s[j], return solve(i+1, j-1) + 2.
  4. Otherwise, return max(solve(i+1, j), solve(i, j-1)).
  5. Use a memo table to cache results for each (i, j) pair.
  6. Call solve(0, n-1) for the final answer.

Example Walkthrough

1Start: solve(0, 4). s[0]='b'==s[4]='b', match!
0
b
i=0
1
b
2
b
3
a
4
j=4
b
1/6

Code

The recursion stack can go up to O(n) deep, adding overhead from function calls. What if we filled the DP table iteratively, bottom-up, eliminating all recursion overhead?

Approach 2: Bottom-Up Dynamic Programming

Intuition

The memoization approach reveals the subproblem structure clearly: dp[i][j] depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1]. All three involve either incrementing i or decrementing j (or both). So if we fill the table in the right order, every dependency is already computed when we need it.

The trick is to iterate by substring length. Start with substrings of length 1 (single characters, all palindromes of length 1), then length 2, then length 3, and so on. For each length, sweep across all starting positions. By the time we compute dp[i][j] for a substring of length len, all shorter substrings are already filled in.

Algorithm

  1. Create a 2D table dp of size n x n, initialized to 0.
  2. Fill the diagonal: dp[i][i] = 1 for all i (every single character is a palindrome).
  3. For each substring length len from 2 to n:
    • For each starting index i from 0 to n - len:
      • Set j = i + len - 1 (the ending index).
      • If s[i] == s[j], set dp[i][j] = dp[i+1][j-1] + 2.
      • Otherwise, set dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  4. Return dp[0][n-1].

Example Walkthrough

1Step 1: Initialize. Each single char is a palindrome of length 1.
0
b
1
b
2
b
3
a
4
b
1/8

Code

We're using O(n^2) space for the DP table, but when computing row i, we only need row i+1. Can we reduce space from O(n^2) to O(n) by keeping just one row?

Approach 3: Space-Optimized DP

Intuition

Look at the dependencies again. dp[i][j] depends on dp[i+1][j-1] (row below, one column left), dp[i+1][j] (row below, same column), and dp[i][j-1] (same row, one column left). So when filling row i, we only ever look at row i+1. Once we're done with row i, we never need row i+2 or any earlier row again. This means we can compress the entire 2D table into a single 1D array of length n.

The trick is careful handling of the dp[i+1][j-1] dependency. When we update dp[j] in our 1D array (processing left to right), we're overwriting what used to be the old row's value. We need to save that old value in a prev variable before it gets overwritten.

Algorithm

  1. Create a 1D array dp of size n, initialized to 1 (each character is a palindrome of length 1).
  2. Iterate i from n-2 down to 0 (processing rows bottom to top):
    • Initialize prev = 0 to store the old dp[j-1] before it's overwritten.
    • For each j from i+1 to n-1:
      • Save temp = dp[j] (this is the old dp[i+1][j]).
      • If s[i] == s[j], set dp[j] = prev + 2.
      • Otherwise, set dp[j] = max(dp[j], dp[j-1]).
      • Set prev = temp.
  3. Return dp[n-1].

Example Walkthrough

1Initialize dp = [1, 1, 1, 1] for s = "cbbd"
0
1
1
1
2
1
3
1
1/6

Code