Problem Description

• LeetCode 516 Longest Palindromic Subsequence

The "Longest Palindromic Subsequence" problem asks you to find the length of the longest subsequence in a given string that reads the same forward and backward.

Key Points:

• A subsequence is derived by deleting some (possibly zero) characters without changing the order of remaining characters
• A palindrome reads the same forward and backward
• We need to find the maximum length of such a subsequence

Example: "bbbab"

• Possible palindromic subsequences: "b", "bb", "bbb", "bbbb", "aba", "bab"
• Longest: "bbbb" with length 4
• Result: 4

Note: Unlike substrings, subsequences don't need to be contiguous, making this problem more complex than finding palindromic substrings.

Algorithm Walkthrough

This solution uses dynamic programming with a 2D table where dp[i][j] represents the length of the longest palindromic subsequence in the substring from index i to j.

Core DP Logic

State Definition

dp[i][j] = length of longest palindromic subsequence in s[i...j]

Base Case

dp[i][i] = 1 - A single character is always a palindrome of length 1

Recurrence Relation

For substring s[i...j]:

1. If characters match (s[i] == s[j]):

   dp[i][j] = 2 + dp[i+1][j-1]
   

   • Include both matching characters
   • Add 2 to the longest palindrome in the inner substring

2. If characters don't match (s[i] != s[j]):

   dp[i][j] = max(dp[i+1][j], dp[i][j-1])
   

   • Try excluding the left character OR the right character
   • Take the maximum of both options

Bottom-Up Filling Strategy

The algorithm fills the DP table in a specific order to ensure dependencies are resolved:

1. Direction: Process from bottom-right to top-left (i from n-1 to 0)
2. Inner loop: For each i, process j from i+1 to n-1
3. Dependency: dp[i][j] depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1]

Example Trace

For string "bbbab":

Initial: dp[i][i] = 1 for all i

i=4, j=4: dp[4][4] = 1 (base case)
i=3, j=4: s[3]='a', s[4]='b' ≠ → dp[3][4] = max(dp[4][4], dp[3][3]) = 1
i=2, j=3: s[2]='b', s[3]='a' ≠ → dp[2][3] = max(dp[3][3], dp[2][2]) = 1
i=2, j=4: s[2]='b', s[4]='b' = → dp[2][4] = 2 + dp[3][3] = 3
i=1, j=2: s[1]='b', s[2]='b' = → dp[1][2] = 2 + dp[2][1] = 2
...
Final: dp[0][4] = 4

The algorithm systematically builds up solutions for larger substrings using previously computed results for smaller substrings.

Complexity Analysis

Time Complexity: O(n²)

• Nested loops: Outer loop runs n times, inner loop runs up to n times
• Each cell: O(1) operations (character comparison and arithmetic)
• Total: O(n²) cells × O(1) per cell = O(n²)

Space Complexity: O(n²)

• 2D DP table: dp[n][n] stores results for all possible substrings
• Optimization possible: Can reduce to O(n) space using rolling array technique, but increases code complexity

Full Solution

This solution demonstrates a classic dynamic programming approach to sequence problems. The key insight is recognizing that the problem has optimal substructure - the longest palindromic subsequence of a string can be constructed from the solutions of smaller substrings. The bottom-up approach ensures all dependencies are resolved before they're needed, making the algorithm both efficient and easy to understand.

class Solution {
    public int longestPalindromeSubseq(String s) {
        // Get the length of the input string
        int n = s.length();
        // Initialize a 2D array to store the length of the longest palindromic subsequence
        int[][] dp = new int[n][n];

        // Iterate over the substrings in reverse order to fill in the dp table bottom-up
        for (int i = n-1; i >= 0; i--) {
            // Base case: the longest palindromic subsequence of a single character is 1
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                // If the two characters match, the longest palindromic subsequence can be extended by two
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + dp[i+1][j-1];
                } else {
                    // Otherwise, we take the maximum of the two possible substrings
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        // The length of the longest palindromic subsequence is in the top-right corner of the dp table
        return dp[0][n-1];
    }
}