Command Palette

Search for a command to run...

Hectal
Problem 31.5 · DP on Strings and SequencesMedium

Longest Palindromic Subsequence

PatternInterval DPDP on Two Strings

What it teaches: Interval DP on one string: peel matching ends.

Practise it on judges as “Longest Palindromic Subsequence”.

The problem

Return the length of the longest palindromic subsequence of s.

Example 1

Input: s = "bbbab"
Output: 4

"bbbb".

Constraints

  • 1 ≤ n ≤ 1000

Pattern clues in the wording

  • → Palindrome + subsequence

These clues point to Interval DP: dp[i][j] is the answer for the range i..j, built from smaller ranges by trying every split point.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int longestPalindromeSubseq(String s) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "bbbab"
4
2
s = "cbbd"
2

From slow to fast

Approaches

1. Interval DP · O(n²)
1

Interval DP

Time O(n²) Space O(n²)

i from n − 1 down to 0, j from i up: dp[i][i] = 1; ends equal → dp[i + 1][j − 1] + 2; else max(dp[i + 1][j], dp[i][j − 1]).

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

Verdict: Fill order makes inner intervals ready.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single character
  • All distinct (1)

Mistakes people make

  • Confusing it with the longest palindromic substring (contiguous).

Interview

Follow-up questions

Minimum insertions to make s a palindrome?