Given a string, return the length of the longest palindromic subsequence in the string. For example, given the following string: MAPTPTMTPA Return 7, since the longest palindromic subsequence in the string is APTMTPA. Recall that a subsequence of a string does not have to be contiguous! Your algorithm should run in O(n^2) time and space. Solution in java, javascript and python
Java:
public class LongestPalindromicSubsequence {
public static 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] = 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];
}
public static void main(String[] args) {
String input = "MAPTPTMTPA";
int result = longestPalindromeSubseq(input);
System.out.println(result); // Output: 7
}
}
JavaScript:
function longestPalindromeSubseq(s) {
const n = s.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s.charAt(i) === s.charAt(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];
}
const input = "MAPTPTMTPA";
const result = longestPalindromeSubseq(input);
console.log(result); // Output: 7
Python:
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
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])
return dp[0][n - 1]
input_str = "MAPTPTMTPA"
result = longestPalindromeSubseq(input_str)
print(result) # Output: 7