Longest Palindromic Subsequence

Link: Leetcode - Longest Palindromic Subsequence

Problem Statement

Given a string s, return the length of the longest palindromic subsequence in s.

Intuition

A subsequence is different from a substring. We want the longest sequence that reads the same forward and backward, but characters do not have to be contiguous.

We reduce this problem to finding the Longest Common Subsequence (LCS) between:

This works because a palindrome is equal to its reverse.

Example

s = "bbabcbcab"
rev = "bacbcbabb"

LCS of s and rev = "babcbab" → length = 7

Answer = 7

Step-by-Step Approaches

We will follow this flow:

1. Recursion
2. Memoization
3. Tabulation
4. Space Optimization

1. Recursion (Top-Down without Memoization)

Java Code (Recursive LCS of s and reverse(s))

class Solution {
    public int longestPalindromeSubseq(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        return lcs(s, rev, s.length(), s.length());
    }

    private int lcs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;
        
        if (s1.charAt(i - 1) == s2.charAt(j - 1))
            return 1 + lcs(s1, s2, i - 1, j - 1);
        else
            return Math.max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1));
    }
}

2. Memoization (Top-Down with Caching)

Java Code (DP Memoized)

class Solution {
    public int longestPalindromeSubseq(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        
        for (int[] row : dp) Arrays.fill(row, -1);
        
        return lcs(s, rev, n, n, dp);
    }

    private int lcs(String s1, String s2, int i, int j, int[][] dp) {
        if (i == 0 || j == 0) return 0;
        
        if (dp[i][j] != -1) return dp[i][j];
        
        if (s1.charAt(i - 1) == s2.charAt(j - 1))
            return dp[i][j] = 1 + lcs(s1, s2, i - 1, j - 1, dp);
        else
            return dp[i][j] = Math.max(lcs(s1, s2, i - 1, j, dp), lcs(s1, s2, i, j - 1, dp));
    }
}

3. Tabulation (Bottom-Up DP)

Java Code

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();

        int[][] dp = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][n];
    }
}

4. Space Optimization

You only need two 1D arrays (previous and current row).

Java Code (Space Optimized)

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();

        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                    curr[j] = 1 + prev[j - 1];
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            prev = curr.clone();
        }

        return prev[n];
    }
}

Time and Space Complexity

Approach Time Complexity Space Complexity
Recursion O(2^n) O(n) (stack)
Memoization O(n^2) O(n^2)
Tabulation O(n^2) O(n^2)
Space Optimized O(n^2) O(n)

Dry Run

s = "bbbab"
rev = "babbb"

dp LCS matrix will build and final result will be dp[5][5] = 4 (bbbb is a subsequence)

Answer = 4

Summary