## Algorithm

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

Example 2:

```Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
```

Constraints:

• `1 <= s.length <= 1000`
• `s` consists only of lowercase English letters.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define IDX(I, J, L) ((I) * (L) + J)
​
int helper(char *s, int i, int j, int l, int *memo) {
int k1, k2, k;

if (i > j) return 0;
if (i == j) return 1;

if (memo[IDX(i, j, l)]) return memo[IDX(i, j, l)];

if (s[i] == s[j]) {
k = helper(s, i + 1, j - 1, l, memo) + 2;
} else {
// head and tail not match, try reducing tail or shifting head
k1 = helper(s, i, j - 1, l, memo);
k2 = helper(s, i + 1, j, l, memo);
k = k1 > k2 ? k1 : k2;
}
memo[IDX(i, j, l)] = k;

return k;
}
int longestPalindromeSubseq(char* s) {
int *memo, l;

if (!s || !*s) return 0;

l = strlen(s);

memo = calloc(l * l, sizeof(int));

l = helper(s, 0, l - 1, l, memo);

free(memo);

return l;
}
``````
Copy The Code &

Input

cmd
s = "bbbab"

Output

cmd
4

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String longestPalindrome(String s) {
int start = 0;
int end = 0;
for (int i = 0; i  <  s.length(); i++) {
int lenOne = helper(s, i, i);
int lenTwo = helper(s, i, i + 1);
int maxLength = Math.max(lenOne, lenTwo);
if (maxLength > end - start) {
start = i - (maxLength - 1) / 2;
end = i + maxLength / 2;
}
}
return s.substring(start, end + 1);
}

private int helper(String s, int left, int right) {
while (left >= 0 && right  <  s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
``````
Copy The Code &

Input

cmd
s = "bbbab"

Output

cmd
4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const longestPalindromeSubseq = function(s) {
const n = s.length
const dp = Array.from({ length: n }, () => Array(n).fill(0))
for(let i = 0; i  <  n; i++) dp[i][i] = 1
for(let len = 2; len  < = n; len++) {
for(let i = 0; i + len - 1  <  n; i++) {
const j = i + len - 1
if(s[i] === s[j]) dp[i][j] = 2 + dp[i + 1][j - 1]
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
}
}
return dp[0][n - 1]
};
``````
Copy The Code &

Input

cmd
s = "cbbd"

Output

cmd
2

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def longestPalindromeSubseq(self, s):
dp = [[0 for j in range(len(s))] for i in range(len(s))]
for i in range(len(s) - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, len(s)):
dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j] else max(dp[i + 1][j], dp[i][j - 1])
return dp[0][len(s) - 1]
``````
Copy The Code &

Input

cmd
s = "bbbab"

Output

cmd
4