Skip to content
On this page

516. Longest Palindromic Subsequence share

Problem Statement:

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

  • 1 <= s.length <= 1000
  • s consists only of lowercase English letters.

Solution:

java
public int longestPalindromeSubseq(String s) {
    String str1 = s,
        str2 = new StringBuilder(s).reverse().toString();
    int m = str1.length(),
        n = str2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < m + 1; i++)
    for (int j = 0; j < n + 1; j++) {
        if (i == 0 || j == 0)
        dp[i][j] = 0;
        else if (str1.charAt(i - 1) == str2.charAt(j - 1))
        dp[i][j] = 1 + dp[i - 1][j - 1];
        else
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
    return dp[m][n];
}

...


Released under the MIT License.