Problem
You are given a strings. Return the length of the longest palindromic subsequence.
Unlike a substring, a subsequence does not need to contain consecutive characters. Characters can be skipped while maintaining their original order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "bbbab"Output
4Explanation
One longest palindromic subsequence is:"bbbb"Solution
This problem can be solved using Recursion with Memoization. We consider a range of characters fromstart to end.
If the characters at both ends are equal, we can include both characters in the palindromic subsequence. We then recursively find the longest palindromic subsequence between them.
If the characters are different, both characters cannot be part of the palindrome at the same time. We have two choices: skip the character at
start or skip the character at end.
The same
start and end range can be reached multiple times, so we store the calculated result in a memoization table.
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] memo = new int[n][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return longest(s, 0, n - 1, memo);
}
private int longest(String s, int start, int end, int[][] memo) {
// No characters left.
if (start > end) {
return 0;
}
// One character is a palindrome.
if (start == end) {
return 1;
}
// Return the cached result.
if (memo[start][end] != -1) {
return memo[start][end];
}
// Include both characters.
if (s.charAt(start) == s.charAt(end)) {
return memo[start][end] = 2 + longest(s, start + 1, end - 1, memo);
}
// Skip either the left or right character.
return memo[start][end] = Math.max(longest(s, start + 1, end, memo), longest(s, start, end - 1, memo));
}
}
Complexity
There are at mostO(n²) different combinations of start and end, and each state is calculated only once.
Therefore, the time complexity is
O(n²). The memoization table requires O(n²) space.
Tabulation Approach
We can also solve the problem using bottom-up Dynamic Programming.Let
dp[i][j] represent the length of the longest palindromic subsequence between index i and index j.
Every single character is a palindrome of length
1, so:
dp[i][i] = 1dp[i][j] = 2 + dp[i + 1][j - 1]dp[i][j] = max( dp[i + 1][j], dp[i][j - 1] )class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
// Every single character is a palindrome.
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// Build solutions for increasing ranges.
for (int start = n - 1; start >= 0; start--) {
for (int end = start + 1; end < n; end++) {
if (s.charAt(start) == s.charAt(end)) {
dp[start][end] = 2 + dp[start + 1][end - 1];
} else {
dp[start][end] = Math.max(dp[start + 1][end], dp[start][end - 1]);
}
}
}
return dp[0][n - 1];
}
}
Complexity
The DP table containsn × n states, and each state is calculated once, resulting in O(n²) time complexity and O(n²) space complexity.
Space Optimized Approach
In the tabulation approach, each state only depends on values from the current row and the previous row. Therefore, we can reduce the space complexity fromO(n²) to O(n).
We use a one-dimensional
dp array and keep track of the previous diagonal value using a variable.
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[] dp = new int[n];
for (int start = n - 1; start >= 0; start--) {
dp[start] = 1;
int previous = 0;
for (int end = start + 1; end < n; end++) {
int temp = dp[end];
if (s.charAt(start) == s.charAt(end)) {
dp[end] = 2 + previous;
} else {
dp[end] = Math.max(dp[end], dp[end - 1]);
}
previous = temp;
}
}
return dp[n - 1];
}
}
Complexity
The optimized approach still processes allO(n²) states, but only stores one DP array, resulting in O(n²) time complexity and O(n) space complexity.