Question

Formatted question description: https://leetcode.ca/all/516.html

 516. Longest Palindromic Subsequence

 Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

 Example 1:
 Input:

 "bbbab"
 Output:
 4
 One possible longest palindromic subsequence is "bbbb".


 Example 2:
 Input:

 "cbbd"
 Output:
 2
 One possible longest palindromic subsequence is "bb".


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

Algorithm

dp[i][j] is [i,j] longest Palindromic Subsequence in range [i,j]

              /  dp[i + 1][j - 1] + 2                       if (s[i] == s[j])

dp[i][j] =

              \  max(dp[i + 1][j], dp[i][j - 1])        if (s[i] != s[j])

Code

Java

public class Longest_Palindromic_Subsequence {

    public 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) {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[0][n - 1];
        }
    }

}

All Problems

All Solutions