# Solution For Longest Palindromic Subsequence

Problem: 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.

Examples:
Input: “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.

Input: “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.

Solution:
This problem can be solved using dynamic programming. Let dp[i][j] represent the length of longest palindromic subsequence between indices i and j (inclusive). The base case is when i == j, in which the length of the palindromic subsequence is 1. Then, we can fill up the dp array using the following recurrence relation:

if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The first case handles when the first and last characters are the same, in which case we add 2 to the length of the longest palindromic subsequence between indices i+1 and j-1. The second case handles when the first and last characters are different, in which case we take the maximum between the length of longest palindromic subsequence between indices i+1 and j, and the length of longest palindromic subsequence between indices i and j-1.

Finally, the answer is in dp[0][n-1], where n is the length of the string s.

Here’s the Python code:

def longestPalindromeSubseq(s: str) -> int:
n = len(s)
dp = [[0]*n for _ in range(n)] for i in range(n):
dp[i][i] = 1
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]

## Step by Step Implementation For Longest Palindromic Subsequence

```public class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}

/*
The idea is to build a 2D dp array where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i..j].

We start by initializing the diagonal elements of the dp array to 1 because the longest palindromic subsequence of a string of length 1 is itself.

Then, we fill in the rest of the dp array according to the following rules:

If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2
If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The dp[0][n-1] element of the array will then contain the length of the longest palindromic subsequence in the entire string s.
*/```
```def longestPalindromeSubseq(s):
# Base case: s is empty
if not s:
return 0

# Initialize a 2D array of size len(s) x len(s).
# dp[i][j] will be the length of the longest palindromic subsequence
# in s[i:j+1].
dp = [[0] * len(s) for _ in range(len(s))]

# Consider each substring s[i:j+1]. In each iteration, we build
# on the results from the previous iteration to calculate
# dp[i][j].
for j in range(len(s)):
# The longest palindromic subsequence of length 1 is just the
# character at that index.
dp[j][j] = 1

# Consider each character s[i] before s[j].
for i in reversed(range(j)):
# If the characters at indices i and j match, then we can
# extend the palindromic subsequence by 2. Otherwise, we
# take the maximum of the two subsequences without s[i]
# and without s[j].
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])

# The length of the longest palindromic subsequence will be in
# dp[0][len(s)-1].
return dp[0][len(s)-1]```
```var longestPalindromeSubseq = function(s) {
// create a 2D array to store the results of our subproblems
// each subproblem is the length of the longest palindromic subsequence
// for the substring of s starting at index i and ending at index j
const dp = Array(s.length).fill(null).map(() => Array(s.length).fill(0));

// base case: a palindromic subsequence of length 1 is just the character itself
for (let i = 0; i < s.length; i++) {
dp[i][i] = 1;
}

// iterate over the length of the string, starting with substrings of length 2
for (let len = 2; len <= s.length; len++) {
// for each possible substring of length len, iterate over the start and end indices
for (let i = 0; i <= s.length - len; i++) {
const j = i + len - 1;
// if the start and end characters are the same, we can extend the longest
// palindromic subsequence by one character
if (s[i] === s[j]) {
dp[i][j] = dp[i+1][j-1] + 2;
// if the start and end characters are not the same, we take the maximum
// of the longest palindromic subsequences that don't include those characters
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}

// the result is the length of the longest palindromic subsequence for the entire string
return dp[0][s.length - 1];
};```
```class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
// Create a 2D array to store results of subproblems
int dp[n][n];

// Strings of length 1 are palindrome of length 1
for (int i = 0; i < n; i++)
dp[i][i] = 1;

// Build the table in bottom up fashion
for (int cl = 2; cl <= n; cl++)
{
for (int i = 0; i < n-cl+1; i++)
{
int j = i+cl-1;
if (s[i] == s[j] && cl == 2)
dp[i][j] = 2;
else if (s[i] == s[j])
dp[i][j] =  dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
}
}
return dp[0][n-1];
}
};```
```using System;

public class Solution {

public int LongestPalindromeSubseq(string s) {

// base case

if (s.Length == 0) {

return 0;

}

// create a 2D array to store the subproblem solutions

int[,] dp = new int[s.Length, s.Length];

// fill in the array in a bottom-up fashion

for (int i = s.Length - 1; i >= 0; i--) {

for (int j = i; j < s.Length; j++) {

// base case

if (i == j) {

dp[i, j] = 1;

}

// if the ith and jth characters are equal, then the

// longest palindromic subsequence will be 2 + the

// longest palindromic subsequence of the string

// without those characters

else if (s[i] == s[j]) {

dp[i, j] = 2 + dp[i + 1, j - 1];

}

// otherwise, the longest palindromic subsequence will

// be the maximum of the two subproblems without the

// ith or jth character

else {

dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);

}

}

}

// return the solution to the original problem

return dp[0, s.Length - 1];

}

}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]