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`

.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:4Explanation:One possible longest palindromic subsequence is "bbbb".

**Example 2:**

Input:s = "cbbd"Output:2Explanation: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 ^{2})** 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]; } }

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 ? **Che****ck Top Interview Questions category**.