AlgoMaster Logo

Longest Palindromic Subsequence

mediumFrequency9 min readUpdated June 23, 2026

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.

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, at least one of them is excluded, so we drop the first or the last character and take the better result. This gives a recursive structure with overlapping subproblems, which points to dynamic programming.

Key Constraints:

  • 1 <= s.length <= 1000 --> With n up to 1000, an O(n^2) solution runs about 1 million operations, which is fast enough. O(n^3) would be about 1 billion operations and is too slow, so we need O(n^2) or better.
  • s consists only of lowercase English letters --> The answer fits comfortably in a 32-bit integer (at most 1000), so there are no overflow concerns.

Approach 1: Recursive Brute Force with Memoization

Intuition

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, and each call adds function-call overhead. The next approach fills the same table iteratively, bottom-up, which removes the recursion entirely.

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.

One ordering that satisfies this is 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. Every dependency of dp[i][j] is a strictly shorter substring, so by the time we reach 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

The DP table uses O(n^2) space, but computing row i only reads row i+1. The next approach keeps a single row and reduces space to O(n).

Approach 3: Space-Optimized DP

Intuition

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). When filling row i, we only read row i+1. Once row i is done, no earlier row is needed again, so the entire 2D table compresses into a single 1D array of length n. The array holds row i+1 at the start of each iteration and is updated in place to become row i.

The complication is the dp[i+1][j-1] dependency. Processing j left to right, the value at index j-1 is overwritten to its row-i value before we reach index j. To recover the old row-i+1 value at j-1, we save it in a prev variable on the previous iteration, right before overwriting it.

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

Approach 4: Reduction to Longest Common Subsequence

Intuition

A palindrome reads the same forwards and backwards. So a palindromic subsequence of s is also a subsequence of reverse(s), sitting at the mirrored positions. The longest palindromic subsequence of s is therefore the longest subsequence common to both s and its reverse:

For s = "cbbd", the reverse is "dbbc". The longest common subsequence of "cbbd" and "dbbc" is "bb", length 2, which matches the answer.

This reduction lets you solve the problem with a Longest Common Subsequence routine and no palindrome-specific logic. The asymptotic cost is the same as the direct DP: O(n^2) time and O(n^2) space.

One subtlety: every palindromic subsequence of s maps to a common subsequence of s and reverse(s), and the reverse holds as well, so the two lengths are equal rather than merely related. The lengths match because the position mapping k -> n-1-k turns any palindrome inside s into a matching subsequence inside reverse(s) of the same length.

Algorithm

  1. Let t = reverse(s) and n = s.length.
  2. Build a 2D table dp of size (n+1) x (n+1), initialized to 0. dp[i][j] is the LCS length of the first i characters of s and the first j characters of t.
  3. For i from 1 to n and j from 1 to n:
    • If s[i-1] == t[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
    • Otherwise, set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  4. Return dp[n][n].

Example Walkthrough

1s = "cbbd", reverse(s) = "dbbc". Compute LCS of the two.
0
c
1
b
2
b
3
d
1/6

Code