Longest Palindromic Subsequence

Medium Dynamic Programming Strings Original on LeetCode

Longest Palindromic Subsequence is a medium dynamic programming problem solved with the strings pattern. The best approach, interval dp (one row), runs in O(n²) time and O(n) space. Below are 2 approaches in Java, from lcs with the reversed string up.

Problem

Return the length of the longest subsequence of s that is a palindrome.

Examples

Example 1

Input: s = "bbbab"
Output: 4
Why: bbbb.

Example 2

Input: s = "cbbd"
Output: 2

Constraints

1 <= s.length <= 1000; lowercase letters.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
LCS with the reversed string	`O(n²)`	`O(n²)`
Interval DP (one row)	`O(n²)`	`O(n)`

1LCS with the reversed string

TimeO(n²)

SpaceO(n²)

A palindromic subsequence reads the same backwards, so it is a common subsequence of s and its reverse.

Return LCS(s, reverse(s)).

Java

class Solution {
    public int longestPalindromeSubseq(String s) {
        String r = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = s.charAt(i - 1) == r.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
        return dp[n][n];
    }
}

2Interval DP (one row)

TimeO(n²)

SpaceO(n)

dp[i][j] = LPS of s[i..j]. Equal ends: 2 + dp[i + 1][j - 1]. Otherwise max(dp[i + 1][j], dp[i][j - 1]). Go i from right to left so the needed values are ready, and keep only one row.

For i from n - 1 down: dp[i] = 1; for j > i apply the rule.

Java

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[] dp = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            int diag = 0; // dp[i + 1][j - 1] from the previous row
            for (int j = i + 1; j < n; j++) {
                int old = dp[j];
                dp[j] = s.charAt(i) == s.charAt(j) ? diag + 2 : Math.max(dp[j], dp[j - 1]);
                diag = old;
            }
        }
        return dp[n - 1];
    }
}

Edge cases to test

Single character (1)
Already a palindrome

Hints

Hint 1

LPS(s) = LCS(s, reverse(s)). Or use interval DP on dp[i][j] for s[i..j].

FAQ

What is the best time complexity for Longest Palindromic Subsequence?

Interval DP (one row) runs in O(n²) time and O(n) extra space.

Which pattern does Longest Palindromic Subsequence use?

It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Minimum Insertion Steps to Make a String Palindrome.

Is there a brute force solution for Longest Palindromic Subsequence?

Yes. LCS with the reversed string takes O(n²) time and O(n²) space. A palindromic subsequence reads the same backwards, so it is a common subsequence of s and its reverse.

Which edge cases should I test for Longest Palindromic Subsequence?

Single character (1); Already a palindrome.