Longest Palindromic Subsequence LeetCode Solution

Last updated on October 5th, 2024 at 06:05 pm

Here, We see Longest Palindromic Subsequence LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Amazon, Uber

Level of Question

Medium

Longest Palindromic Subsequence LeetCode Solution

Longest Palindromic Subsequence LeetCode Solution

Problem Statement

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

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”.

1. Longest Palindromic Subsequence LeetCode Solution C++

class Solution {
public:
    int longestPalindromeSubseqTabular(string& s) {
        if(s.empty())
            return 0;
        const 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 l = 1; l < N; l++) {
            for(int i = 0; i < N - l; i++) {
                int j = i + l;
                if((j - i + 1) == 2) {
                    dp[i][j] = 1 + (s[i] == s[j]);
                }
                else {
                    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];
    }

    int longestPalindSubseqRec(vector<vector<int> >& dp, string& s, int i, int j) {
        if(i > j)
            return 0;
        if(i == j)
            return dp[i][j] = 1;
        if(dp[i][j] == -1) {
            if(s[i] == s[j])
                dp[i][j] = 2 + longestPalindSubseqRec(dp, s, i+1, j-1);
            else
                dp[i][j] = max(longestPalindSubseqRec(dp, s, i+1, j),
                               longestPalindSubseqRec(dp, s, i, j-1));
        }
        return dp[i][j];
    }
    
    int longestPalindSubseqRecDriver(string& s) {
        if(s.empty())
                return 0;
        const int N = s.size();
        vector<vector<int> > dp(N, vector<int>(N, -1)); 
        return longestPalindSubseqRec(dp, s, 0, N-1);
    }
    
    int longestPalindromeSubseq(string s) {
        return longestPalindSubseqRecDriver(s);
    }
};

2. Longest Palindromic Subsequence LeetCode Solution Java

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

3. Longest Palindromic Subsequence Solution JavaScript

var longestPalindromeSubseq = function(s) {
    const n = s.length;
    const dp = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = n-1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i+1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
};

4. Longest Palindromic Subsequence Solution Python

class Solution(object):
    def longestPalindromeSubseq(self, s):
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i+1][j-1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])     
        return dp[0][n-1]
Scroll to Top