Longest Palindromic Subsequence LeetCode and InterviewBit Solution

Longest Palindromic Subsequence is the most asked dynamic programming questions 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.

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(n2) and Space Complexity of O(n).

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:

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:

// 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];
    }
}
Longest Palindromic Subsequence LeetCode and InterviewBit Solution

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.

Share your love

Leave a Reply