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 <= 1000sconsists 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]) {
// head and tail match
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;
}
Input
s = "bbbab"
Output
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;
}
}
Input
s = "bbbab"
Output
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]
};
Input
s = "cbbd"
Output
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]
Input
s = "bbbab"
Output
4