Longest Palindromic Subsequence LeetCode and InterviewBit Solution

Longest Palindromic Subsequence is the most asked dynamic programming question in a coding interview for FAANG. So, today we will be discussing the algorithm and how you can solve this question using DP in C++, JAVA, and Python.

Question: Longest Palindromic Subsequence

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

Solution For Longest Palindromic Subsequence

To solve this problem in the most efficient way we need to use a dynamic programming algorithm. We will break the problem into the smallest problem, solve them first, and then use the bottom-up approach to solve bigger problems.

Below Code have a runtime Complexity of O(n²) and Space Complexity of O(n).

//C++ Code Example
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        if (s.empty()) return 0;
        
        vector<vector<int>> longest(s.size(), vector<int>(s.size()));
        for (int len=1; len<=s.size(); len++) {
            for (int i=0; i+len<=s.size(); i++) {
                int j = i+len-1;
                if (i == j) {
                    longest[i][j] = 1;
                } else if (i+1 == j) {
                    longest[i][j] = (s[i] == s[j]) ? 2 : 1;
                } else {
                    int add = s[i] == s[j] ? 2 : 0;
                    longest[i][j] = max(max(longest[i][j-1], longest[i+1][j]), longest[i+1][j-1] + add);
                }
            }
        }
        
        return longest[0].back();
    }
};

Python Solution:

#Python Code Example
class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == s[::-1]:
            return len(s)
        n = len(s)
        dp = [[0 for j in xrange(n)] for i in xrange(n)]
        for i in xrange(n-1, -1, -1):
            dp[i][i] = 1
            for j in xrange(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]

JAVA Solution:

//JAVA Code Example
// Its a Typical DP Problem. All you need is to have a basic Dynamic Programming Knowledge.
public class Solution {
    public int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] a=new int[n][n];
        for(int i=0;i<n;i++) a[i][i]=1;
        return helper(a,0,n-1,s);
    }
    private int helper(int[][] a,int i,int j,String s){
        if(i>j || a[i][j]!=0) return a[i][j];
        if(s.charAt(i)==s.charAt(j)) a[i][j]=helper(a,i+1,j-1,s)+2;
        else a[i][j]=Math.max(helper(a,i,j-1,s),helper(a,i+1,j,s) );
        return a[i][j];
    }
}

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.