Longest Palindromic Subsequence

medium string dp

Problem

Given a string s, return the length of its longest palindromic subsequence — a sequence that reads the same forwards and backwards but is not required to be contiguous.

Inputs = "bbbab"

Output4

"bbbb" is a palindromic subsequence of length 4.

def longest_palindrome_subseq(s):
    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] if length > 2 else 0) + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

function longestPalindromeSubseq(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = 1;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) dp[i][j] = (len > 2 ? dp[i + 1][j - 1] : 0) + 2;
      else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
    }
  }
  return dp[0][n - 1];
}

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = (len > 2 ? dp[i + 1][j - 1] : 0) + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) dp[i][j] = (len > 2 ? dp[i + 1][j - 1] : 0) + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}

Explanation

We want the longest subsequence that reads the same both ways, where letters can be skipped. The idea is to solve it for every slice of the string and build up from tiny slices to the whole thing, storing answers in a table dp[i][j] = best palindrome inside s[i..j].

The key insight is about the two endpoints of a slice. If s[i] and s[j] are the same letter, they can wrap around whatever palindrome lives strictly inside, so dp[i][j] = dp[i+1][j-1] + 2. If they differ, at least one of them is useless, so we drop one side and take the better of dp[i+1][j] or dp[i][j-1].

We start by marking every single character as a palindrome of length 1 (the diagonal dp[i][i] = 1). Then we fill slices of length 2, 3, and up, so the smaller inner answers a slice needs are always ready before we use them.

This works because a palindrome is defined entirely by its outermost pair of characters plus its core, so checking endpoints and reusing inner results covers every case without rechecking.

Example: for "bbbab", the outer bs keep matching and wrapping the inner bs, building up "bbbb" of length 4, which lands in dp[0][n-1].

Time: O(n²) Space: O(n²)