Longest Palindromic Subsequence

Step 1: Look at the two ends

Take the substring s[i .. j] and compare its first and last characters.

• They are equal: both can be the outer pair of the palindrome. The best answer is 2 plus the best answer for the inside, s[i+1 .. j-1].
• They differ: they cannot both be used. Drop one of them and keep the better result: max(best(i+1, j), best(i, j-1)).

Step 2: Store the answers in a table

Those rules call the same smaller substrings many times, so store them: dp[i][j] is the answer for s[i .. j]. A single character has dp[i][i] = 1.

Step 3: Fill it in the right order

dp[i][j] depends on rows below it (i + 1) and columns left of it (j - 1). So fill rows from the bottom up, and each row from left to right. The answer is dp[0][n-1].

The finished table for s = "bbbab". Row i, column j is the answer for s[i .. j].

For example, dp[0][4]: s[0] = s[4] = b, so it is dp[1][3] + 2 = 2 + 2 = 4.

The outer loop goes from the last row up, so every cell it reads is already filled.

public class LongestPalindromeSubsequence {

    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];           // dp[i][j]: answer for s[i..j]
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;                     // one character is a palindrome
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;   // both ends join the inner answer
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);   // drop one end
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));   // 4
        System.out.println(longestPalindromeSubseq("cbbd"));    // 2
    }
}

• Time: O(n²): one constant-time step per cell.
• Space: O(n²); keeping only two rows brings it to O(n).

The answer also equals the longest common subsequence of s and its reverse; see Longest Common Subsequence. For the longest palindromic substring, see Manacher's Algorithm.