# 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`.

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

```//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.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[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];
}
}```