Longest Palindromic Subsequence

Time: O(n^2)

Space: O(n^2)

Intuition

LPS(s) = LCS(s, reverse(s)). Alternatively, dp[i][j] = LPS of s[i..j]. If s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2. Else: dp[i][j]=max(dp[i+1][j], dp[i][j-1]).

Algorithm

1dp[i][j] = 1 for all i (single char palindrome).
2For length l from 2 to n: for each (i,j) with j=i+l-1: if s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2.
3Else: dp[i][j]=max(dp[i+1][j], dp[i][j-1]).
4Return dp[0][n-1].

Example Walkthrough

Input: s = "bbabcbcab"

1.LPS = "babcbab" length 7, or use LCS with reverse.

Output: 7

Common Pitfalls

•Fill dp bottom-up by increasing subproblem length, not by row.

Longest Palindromic Subsequence.java

Java

// Approach: DP. LPS(s) = LCS(s, reverse(s)), or direct DP on reversed s.
// dp[i][j] = LPS of s[i..j].
// Time: O(n^2) Space: O(n^2)
class Solution {
    public int longestPalinSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        // Initialize diagonal elements (single characters)
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;

        // Fill the dp table
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j) && len == 2)
                    dp[i][j] = 2;
                else if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        return dp[0][n - 1];
    }
}

Was this solution helpful?