Welcome to Subscribe On Youtube

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];
            }
        }
    
    }
    
    
  • class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            int n = s.size();
            vector<vector<int>> dp(n, vector<int>(n, 0));
            for (int i = 0; i < n; ++i) {
                dp[i][i] = 1;
            }
            for (int j = 1; j < n; ++j) {
                for (int i = j - 1; i >= 0; --i) {
                    if (s[i] == s[j]) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[0][n - 1];
        }
    };
    
  • class Solution:
        def longestPalindromeSubseq(self, s: str) -> int:
            n = len(s)
            dp = [[0] * n for _ in range(n)]
            for i in range(n):
                dp[i][i] = 1
            for j in range(1, n):
                for i in range(j - 1, -1, -1):
                    if s[i] == s[j]:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
            return dp[0][-1]
    
    ############
    
    class Solution(object):
      def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        dp = [1] * n
        for j in range(1, len(s)):
          pre = dp[j]
          for i in reversed(range(0, j)):
            tmp = dp[i]
            if s[i] == s[j]:
              dp[i] = 2 + pre if i + 1 <= j - 1 else 2
            else:
              dp[i] = max(dp[i + 1], dp[i])
            pre = tmp
        return dp[0]
    
    

All Problems

All Solutions