Problem Statement: Longest Palindromic Subsequence
A palindromic string is a string that is equal to its reverse. For example: “Nitin” is a palindromic string. Now the question states to find the length of the longest palindromic subsequence of a string. It is that palindromic subsequence of the given string with the greatest length. We need to print the length of the longest palindromic subsequence.
Pre-req: Longest Common Subsequence
Examples
Example:
There can be many subsequences like “b”, “ba”,”bbb” but “bbbb” is the subsequence that is a palindrome and has the greatest length.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Tabulation Approach
Algorithm / Intuition
We are given a string S, the simplest approach will be to generate all the subsequences and store them, then manually find out the longest palindromic subsequence.
This naive approach will give us the correct answer but to generate all the subsequences, we will require exponential ( 2n ) time. Therefore we will try some other approaches.
Using Dynamic Programming
We can use the approach discussed in the article Longest Common Subsequence, to find the Longest Palindromic Subsequence.
Intuition:
Let us say that we are given the following string.
The longest palindromic subsequence will be: “babcbab”.
What is special about this string is that it is palindromic (equal to its reverse) and of the longest length.
Now let us write the reverse of str next to it and please think about the highlighted characters.
If we look closely at the highlighted characters, they are nothing but the longest common subsequence of the two strings.
Now, we have taken the reverse of the string for the following two reasons:
- The longest palindromic subsequence being a palindrome will remain the same when the entire string is reversed.
- The length of the palindromic subsequence will also remain the same when the entire string is reversed.
From the above discussion we can conclude:
The longest palindromic subsequence of a string is the longest common subsequence of the given string and its reverse.
Approach:
The algorithm is stated as follows:
- We are given a string (say s), make a copy of it and store it( say string t).
- Reverse the original string s.
- Find the longest common subsequence as discussed in dp-25.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the length of the Longest Common Subsequence
int lcs(string s1, string s2) {
int n = s1.size();
int m = s2.size();
// Create a 2D DP array to store the length of the LCS
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
// Initialize the first row and first column to 0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
}
// Fill in the DP array
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] == s2[ind2 - 1])
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
else
dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
}
}
// The value at dp[n][m] contains the length of the LCS
return dp[n][m];
}
// Function to calculate the length of the Longest Palindromic Subsequence
int longestPalindromeSubsequence(string s) {
// Create a reversed copy of the string
string t = s;
reverse(s.begin(), s.end());
// Call the LCS function to find the length of the Longest Common Subsequence
return lcs(s, t);
}
int main() {
string s = "bbabcbcab";
// Call the longestPalindromeSubsequence function and print the result
cout << "The Length of Longest Palindromic Subsequence is " << longestPalindromeSubsequence(s);
return 0;
}
import java.util.*;
class TUF {
// Function to find the length of the Longest Common Subsequence (LCS)
static int lcs(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// Create a 2D array to store the LCS lengths
int dp[][] = new int[n + 1][m + 1];
// Initialize the dp array with -1
for (int rows[] : dp)
Arrays.fill(rows, -1);
// Initialize the first row and first column with 0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
}
// Fill the dp array using a bottom-up approach
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1))
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
else
dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
}
}
return dp[n][m];
}
// Function to find the length of the Longest Palindromic Subsequence
static int longestPalindromeSubsequence(String s) {
// Create a reversed version of the input string
String reversed = new StringBuilder(s).reverse().toString();
// Calculate the LCS of the original string and its reverse
return lcs(s, reversed);
}
public static void main(String args[]) {
String s = "bbabcbcab";
System.out.print("The Length of Longest Palindromic Subsequence is ");
System.out.println(longestPalindromeSubsequence(s));
}
}
def lcs(s1, s2):
n = len(s1)
m = len(s2)
# Initialize a 2D array to store the length of the LCS
dp = [[-1] * (m + 1) for i in range(n + 1)]
# Initialize the first row and first column with 0
for i in range(n + 1):
dp[i][0] = 0
for i in range(m + 1):
dp[0][i] = 0
# Fill in the dp array using dynamic programming
for ind1 in range(1, n + 1):
for ind2 in range(1, m + 1):
if s1[ind1 - 1] == s2[ind2 - 1]:
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
else:
dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
# The final value in dp will be the length of the LCS
return dp[n][m]
def longestPalindromeSubsequence(s):
# Reverse the input string
t = s
s = s[::-1]
# Find the longest common subsequence between s and its reverse
return lcs(s, t)
def main():
s = "bbabcbcab"
# Calculate and print the length of the longest palindromic subsequence
print("The Length of Longest Palindromic Subsequence is", longestPalindromeSubsequence(s))
if __name__ == "__main__":
main()
function lcs(s1, s2) {
// Get the lengths of the input strings
const n = s1.length;
const m = s2.length;
// Create a 2D array to store the dynamic programming values
const dp = new Array(n + 1).fill(null).map(() => new Array(m + 1).fill(-1));
// Initialize the first row and first column with 0
for (let i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (let i = 0; i <= m; i++) {
dp[0][i] = 0;
}
// Fill the dp array using dynamic programming
for (let ind1 = 1; ind1 <= n; ind1++) {
for (let ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] === s2[ind2 - 1]) {
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
} else {
dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
}
}
}
// Return the length of the LCS
return dp[n][m];
}
// Function to find the length of the Longest Palindromic Subsequence of a string
function longestPalindromeSubsequence(s) {
// Create a copy of the input string and reverse it
const t = s.split('').reverse().join('');
// Find the LCS between the original and reversed strings
return lcs(s, t);
}
// Main function
function main() {
const s = "bbabcbcab";
// Call the longestPalindromeSubsequence function and print the result
console.log("The Length of Longest Palindromic Subsequence is " + longestPalindromeSubsequence(s));
}
// Call the main function to start the program
main();
Output: The Length of Longest Palindromic Subsequence is 7
Complexity Analysis
Time Complexity: O(N*N)
Reason: There are two nested loops
Space Complexity: O(N*N)
Reason: We are using an external array of size ‘(N*N)’. Stack Space is eliminated.
Space Optimization Approach
Algorithm / Intuition
If we closely we are using two rows: dp[ind1-1][ ], dp[ind][ ],
So we are not required to contain an entire array, we can simply have two rows prev and cur where prev corresponds to dp[ind-1] and cur to dp[ind].
After declaring prev and cur, replace dp[ind-1] to prev and dp[ind] with cur and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the length of the Longest Common Subsequence
int lcs(string s1, string s2) {
int n = s1.size();
int m = s2.size();
// Create two arrays to store the previous and current rows of DP values
vector<int> prev(m + 1, 0), cur(m + 1, 0);
// Base Case is covered as we have initialized the prev and cur to 0.
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] == s2[ind2 - 1])
cur[ind2] = 1 + prev[ind2 - 1];
else
cur[ind2] = max(prev[ind2], cur[ind2 - 1]);
}
// Update the prev array with the current values
prev = cur;
}
// The value at prev[m] contains the length of the LCS
return prev[m];
}
// Function to calculate the length of the Longest Palindromic Subsequence
int longestPalindromeSubsequence(string s) {
// Create a reversed copy of the string
string t = s;
reverse(s.begin(), s.end());
// Call the LCS function to find the length of the Longest Common Subsequence
return lcs(s, t);
}
int main() {
string s = "bbabcbcab";
// Call the longestPalindromeSubsequence function and print the result
cout << "The Length of Longest Palindromic Subsequence is " << longestPalindromeSubsequence(s);
return 0;
}
import java.util.*;
class TUF {
// Function to find the length of the Longest Common Subsequence (LCS)
static int lcs(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// Create two arrays to store the LCS lengths
int[] prev = new int[m + 1];
int[] cur = new int[m + 1];
// Base Case: Initialized to 0, as no characters matched yet.
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1))
cur[ind2] = 1 + prev[ind2 - 1];
else
cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
}
// Update prev array to store the current values
prev = cur.clone();
}
return prev[m];
}
// Function to find the length of the Longest Palindromic Subsequence
static int longestPalindromeSubsequence(String s) {
// Create a reversed version of the input string
String reversed = new StringBuilder(s).reverse().toString();
// Calculate the LCS of the original string and its reverse
return lcs(s, reversed);
}
public static void main(String args[]) {
String s = "bbabcbcab";
System.out.print("The Length of Longest Palindromic Subsequence is ");
System.out.println(longestPalindromeSubsequence(s));
}
}
def lcs(s1, s2):
n = len(s1)
m = len(s2)
# Initialize two lists, prev and cur, for dynamic programming
prev = [0] * (m + 1)
cur = [0] * (m + 1)
# Base Case is covered as we have initialized the prev and cur to 0.
for ind1 in range(1, n + 1):
for ind2 in range(1, m + 1):
if s1[ind1 - 1] == s2[ind2 - 1]:
cur[ind2] = 1 + prev[ind2 - 1]
else:
cur[ind2] = max(prev[ind2], cur[ind2 - 1])
prev = cur[:] # Update prev to be a copy of cur for the next iteration
# The final value in prev will be the length of the LCS
return prev[m]
def longestPalindromeSubsequence(s):
# Reverse the input string
t = s[::-1]
# Find the length of the longest common subsequence between s and its reverse
return lcs(s, t)
def main():
s = "bbabcbcab"
# Calculate and print the length of the longest palindromic subsequence
print("The Length of Longest Palindromic Subsequence is", longestPalindromeSubsequence(s))
if __name__ == "__main__":
main()
function lcs(s1, s2) {
// Get the lengths of the input strings
const n = s1.length;
const m = s2.length;
// Create two arrays, prev and cur, to store dynamic programming values
let prev = new Array(m + 1).fill(0);
let cur = new Array(m + 1).fill(0);
// Base case is covered as we have initialized prev and cur to 0.
// Fill the cur array using dynamic programming
for (let ind1 = 1; ind1 <= n; ind1++) {
for (let ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] === s2[ind2 - 1]) {
cur[ind2] = 1 + prev[ind2 - 1];
} else {
cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
}
}
// Update prev array with the values from cur for the next iteration
prev = [...cur];
}
// Return the length of the LCS
return prev[m];
}
// Function to find the length of the Longest Palindromic Subsequence of a string
function longestPalindromeSubsequence(s) {
// Create a copy of the input string and reverse it
const t = s.split('').reverse().join('');
// Find the LCS between the original and reversed strings
return lcs(s, t);
}
// Main function
function main() {
const s = "bbabcbcab";
// Call the longestPalindromeSubsequence function and print the result
console.log("The Length of Longest Palindromic Subsequence is " + longestPalindromeSubsequence(s));
}
// Call the main function to start the program
main();
Output: The Length of Longest Palindromic Subsequence is 7
Complexity Analysis
Time Complexity: O(N*N)
Reason: There are two nested loops.
Space Complexity: O(N)
Reason: We are using an external array of size ‘N+1’ to store only two rows.
Video Explanation
Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article