## DEV Community 👩‍💻👨‍💻 is a community of 930,237 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# LeetCode 516. Longest Palindromic Subsequence (javascript solution)

### Description:

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.

### Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

``````var longestPalindromeSubseq = function(s) {
const dp = [...Array(s.length)].map(() => Array(s.length).fill(0))

// Base case
for(let i = 0; i < s.length; i++) {
dp[i][i] = 1
}

for(let i = 1; i < s.length; i++) {
for(let j = 0; j < s.length; j++){
if(j+i < s.length){
// If the end letter and start letter are the same add 2 to the value in the bottom left diagonal. This value is a potential palindrome. If the letters are not equal set the current value to the previous highest palindrome subsequence
dp[j][j+i] = s[j] === s[j + i]
? dp[j+1][j+i-1] + 2
: Math.max(dp[j][j+i-1], dp[j+1][i+j])
}
}
}

return dp[s.length-1]
};
``````

## Top comments (1) Satyagraha

*JAVA | SIMPLE EXPLANATION | DETAILED CODE WITH COMMENTS
*

Simple Explanation of Bottom up DP Approach and Space Optimization. In PART 1, we had discussed Top Down DP approach.

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

//Length of string
int n = s.length();

//Matrix to store results
int[][] dp = new int[n][n];

//For length 1 => result is 1 since it is a palindrome
int i, j;
for(i=0; i<n; i++) {
//For length 1, i and j are same
j=i;
dp[i][j] = 1;
}

//For length 2 => we'll have to check the 2 characters at i and j. If
//they are equal => result is 2. If they are not equal => result is 1.
for(i=0; i<n-1; i++) {
//for length 2, j will be i+1
j=i+1;
if(s.charAt(i) == s.charAt(j)) {
dp[i][j] = 2;
} else {
dp[i][j] = 1;
}
}

//For length 3 to n, we'll fix length in first loop. In second loop,
//we'll fix starting position for that length.
int length;
for(length=3; length<=n; length++) {
//i will go till n-length because j's value will reach equal to n-1
for(i=0; i<n-length+1; i++) {
//Example j = 0+3-1 = 2 => relevant part of string is 0 to 2
j=i+length-1;

//If the 2 characters are equal => lps of middle portion +2 is
if(s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
//Else maximum of the 2 candidates is answer. One candidate
//is the string without last character. Other candidate
//is the string without the first character.
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
}
}
}

return dp[n-1];
}
}
``````

SPACE OPTIMIZATION CODE

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

//Length of string
int n = s.length();

if(n==1) return 1;

//This array will correspond to a particular length of the substring.
//Every position of this array will correspond to the starting position
//in the string for this particular length.
//Every element of thi sarray will correspond to the lps for the combination
//of starting position and length.
int[] secondPrevLengthArray = new int[n];
int[] prevLengthArray = new int[n];

//Initially, secondPrevLengthArray will correspond to length 1
//and prevLengthArray will correspond to length 2

//For length 1 => result is 1 since it is a palindrome
int i, j;
for(i=0; i<n; i++) {
secondPrevLengthArray[i] = 1;
}

//For length 2 => we'll check if the 2 characters are same.
//If they are => result is 2. If they are not => result is 1.
for(i=0; i<n-1; i++) {
j = i+1;
//If the 2 chars are equal => at this starting position and for length 2
//lps is 2
if(s.charAt(i) == s.charAt(j)) {
prevLengthArray[i] = 2;
} else {
prevLengthArray[i] = 1;
}
}

//This array will store results for the current length.
int[] newArr = new int[n];

//Iterate from length 3 to n
int length;
for(length = 3; length<=n; length++) {
//For this length, let us now fix starting position one by one
//i will go till n-length because j's value will reach equal to n-1
for(i=0; i<n-length+1; i++) {
//Example j = 0+3-1 = 2 => relevant part of string is 0 to 2
j = i+length-1;

//If the 2 characters are equal => lps of middle portion +2 is
//answer. Middle portion's length will be 2 less than current length
//So, middle portion's answer will lie in secondPrevLengthArray
if(s.charAt(i) == s.charAt(j)) {
newArr[i] = secondPrevLengthArray[i+1] + 2;
} else {
//Else, it'll be max of the 2 candidates. One is lps when
//string doesn't take into account last character. One is lps
//when string doesn't take into account the first character.
//Since only one character is less => candidates will lie in
//prevLengthArray
newArr[i] = Math.max(prevLengthArray[i], prevLengthArray[i+1]);
}
}
//By now, we'd have filled newArr for particular length. Now, for next
//iteration, this newArr will become prevLengthArray and the current
//prevLengthArray will become secondPrevLengthArray. The current
//secondPrevLengthArray is useless for us now.
copyArray1ToArray2(prevLengthArray, secondPrevLengthArray, n);
copyArray1ToArray2(newArr, prevLengthArray, n);

}

//At the end, our answer will be in prevLengthArray's first element.
//Because, that will correspond to full length with starting position as 0
return prevLengthArray;
}

private static void copyArray1ToArray2(int[] toBeCopied, int[] toBeCopiedInto, int n) {
int i;
for(i=0; i<n; i++) {
toBeCopiedInto[i] = toBeCopied[i];
}
}
}
``````

## 🌚 Browsing with dark mode makes you a better developer by a factor of exactly 40.

It's a scientific fact.