# Leetcode Longest Palindromic Subsequence problem solution

In this Leetcode Longest Palindromic Subsequence problem solution 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.

## Problem solution in Python.

```class Solution:
def longestPalindromeSubseq(self, s):

if not s:
return 0
res = [[0 for i in range(len(s))] for i in range(len(s))]
return self.helper(s, 0, len(s) - 1, res)

def helper(self, inp, s, e, res):
if s == e:
return 1
if s > e:
return 0
if res[s][e]:
return res[s][e]
if inp[s] == inp[e]:
res[s][e] = 2 + self.helper(inp, s + 1, e - 1, res)
else:
res[s][e] = max(self.helper(inp, s + 1, e, res),
self.helper(inp, s, e - 1, res))
return res[s][e]```

## Problem solution in Java.

```class Solution {
public int longestPalindromeSubseq(String s) {

int n = s.length();
StringBuilder b = new StringBuilder();
b.append(s);
b.reverse();
return solve(s, b.toString(), n, n);

}

int solve(String str1, String str2, int n, int m){

int[][] dp = new int[n + 1][m + 1];
//initialize
for(int i = 0; i < n + 1; i++){
for(int j = 0; j < m + 1; j++){
if(i == 0 || j == 0) dp[i][j] = 0;
}
}
//main code
for(int i = 1; i < n + 1; i++){
for(int j = 1; j < m + 1; j++){
if(str1.charAt(i - 1) == str2.charAt(j - 1)){
dp[i][j] = 1 + dp[i - 1][j - 1];
}else{
dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
}
}
}
return dp[n][m];
}
}```

## Problem solution in C++.

```class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n+1,vector<int>(n+1,0));
for(int i=1;i<dp.size();i++)
{
for(int j=1;j<dp.size();j++)
{
if(s[i-1] == s[n-j])
{
dp[i][j] = 1 + dp[i-1][j-1];
}else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][n];
}
};```