Back to DSA
Longest Palindromic Subsequence
mediumGiven a string, compute the length of its longest subsequence that reads the same forwards and backwards. Characters in the subsequence need not be adjacent in the original string.
Examples
Example 1:
Input:
s = "character"Output:
5Explanation: One longest palindromic subsequence is "carac" with length 5.
Example 2:
Input:
s = "abcdef"Output:
1Explanation: No two characters form a palindrome, so the best is any single character.
Hints
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];
}
}Time complexity
O(n^2)Space complexity
O(n^2)