Problem Statement
You are given a String ‘ S’ of a certain length, your task is to find the maximum possible palindromic subsequence that can be obtained from the given string.
Subsequence
A subsequence of a given string is generated by deleting some characters of that string without changing its order.
Example 1:
Input: S = "ABBDCACB" Output: 5
Explanation: From the above string, the Longest possible palindromic subsequence is 5, and the subsequence of the string is “BCACB”.
Example 2:
Input: S = "ANMAQRSLAGHYAGHLAM" Output: 9
Explanation: From the above string, the longest possible palindromic subsequence is 9, and the subsequence of the string is "MALAYALAM."
Approach
In the above problem statement, we are asked to find out the maximum palindromic subsequence that can be obtained from the given string. So, if we could observe the problem statement very keenly, we can encounter that the problem has optimal substructure and overlapping subproblem properties.
Optimal Substructure
A given problem has Optimal Substructure Property if an optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.
Overlapping Subproblems
Dynamic Programming, like Divide and Conquer, combines solutions to subproblems. Dynamic Programming is primarily used when solutions to the same subproblems are required repeatedly. Computed solutions to subproblems are stored in a table in dynamic programming so that they do not have to be recomputed. So, if there are no common (overlapping) subproblems, Dynamic Programming cannot be used because storing the solutions is pointless if they are never needed again.
Approach 1: (Recursion)
This approach is called the naive approach, the idea is to implement the Recursion. For implementing the recursion, we will have two cases:
 If the first and last characters of the strings are the same, then we increment the counter (which means that we had obtained a palindrome) and increment the i pointer and decrement the j pointer
 Consider a situation where the first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values.
We get the maximum value of the string as stated below:
 Deleting the first character and applying the recursion for the remaining entire string S[i+1,j]
 Deleting the last character and applying the recursion for the remaining entire string S[i,j1]
From the above two cases, we are going to pick the maximum value (i.e, maximum palindromic subsequence, which is obtained from the string S).
Time Complexity
For the Naive Approach, the time complexity is going to be as 2^n, as the function call happens for every subroutine.
Note
One thing to be kept in mind is that we should define the base case properly; it may result in a Recursion Depth Exceeded exception.
Recursion calls
From the above figure, we can understand that recursion has to take place for every subroutine call so this may take a huge time to run and to solve the hierarchical model. This is the main reason why we have the time complexity as 2^n.
Below is the Algorithm Explained
Define a function called longest palindromic subsequence and take two Pointers as i and j and assign them at the 0th position of the string and last posting the string, respectively. Now define the base cases stated below:
Base cases
 If S[i]==S[j] (this means that, palindrome encountered), then we will return 1.
 If i > j , this means that if the i pointer exceeds the j pointer, we will simply terminate the process and return 0.
If the S[i] and S[j] are not equal, we will apply the recursion by considering the two possibilities discussed above.
Python Code Using Recursion
# Function to find the Maximum length of the palindromic subsequence
# of given string
def longestPalindromicsubsequence(S, i, j):
# Base case
if i > j: # if i exceeds the j pointer
return 0 # stop the flow
# If the string `S" has only one Unique char, it is a palindrome
if i == j:
return 1 # the maximum length is 1 so we return 1
# If the last character of the string matches the first character
if S[i] == S[j]:
# include the first and last characters in palindrome
# and apply the recursion for the remaining substring `S[i+1, j1]`
return longestPalindromicsubsequence(S, i + 1, j  1) + 2
'''
Consider a situation where the first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
We get the maximum value of the string as stated below:
Deleting the first character and apply the recursion for the remaining entire string S[i+1,j]
Deleting the last character and apply the recursion for the remaining entire string S[i,j1]
'''
# we will simply Return the maximum of the two possible values
return max(longestPalindromicsubsequence(S, i, j  1), longestPalindromicsubsequence(S, i + 1, j))
if __name__ == '__main__': # main function
S = "ABBDCACB" # input of the string
n = len(S) # length of the string
print("The longest palindromic subsequence length is",
longestPalindromicsubsequence(S, 0, n  1))
Output:
'The longest palindromic subsequence length is', 5
Java Code Using Recursion
public class Main // defining the main class
{
//defining the function to find the longest palindromic subsequence
// of a string of given S
public static int longestPalindromicsubsequece(String S, int i, int j)
{
// Base case
if (i > j) { // if the i pointer exceeds the j pointer
return 0;
}
// If the string S has only one unique char, it is a palindrome
if (i == j) {
return 1;// we will return 1
}
// If the first character of the string matches the second character,
if (S.charAt(i) == S.charAt(j))
{
// then we will include the first and last characters in palindrome
// and apply recursion for the remaining substring `S[i+1, j1]`
return longestPalindromicsubsequece(S, i + 1, j  1) + 2;
}
/*
If the first character of the string does not match the last character then we will
1. Delete the last character and apply recursion for the remaining part of the string left
`S[i, j1]`
2. Delete the first character and apply recursion for the remaining substring left
`S[i+1, j]`
*/
return Integer.max( longestPalindromicsubsequece(S, i, j  1), // we will pick the maximum value
longestPalindromicsubsequece(S, i + 1, j));
}
public static void main(String[] args)
{
String S = "ABBDCACB";
int n = S.length();
System.out.print("The length of the longest palindromic subsequence is "
+ longestPalindromicsubsequece(S, 0, n  1));
}
}
Output:
The length of the longest palindromic subsequence is 5
C++ Version Code Using recursion
#include<bits/stdc++.h>
using namespace std;
// defining a function to return the max of two integers
int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the maximum palindromic subsequence of a given string
int longestpalindromicsubsequence(char *S, int i, int j)
{
// If there is only 1 unique character then we will return 1
if (i == j) // since it is a palindrome
return 1;
//2nd base condition, is if there are only two characters present
if (S[i] == S[j] && i + 1 == j)
return 2; // then we will return 2 since the length of the the maximum length of the palindromic Subsequence is 2
// If the first and last chars are equal
if (S[i] == S[j])
return longestpalindromicsubsequence (S, i+1, j1) + 2;
// If the first char and last char dosentare not equal then we will picj the maximum value
return max( longestpalindromicsubsequence(S, i, j1), longestpalindromicsubsequence(S, i+1, j) );
}
/* Driver program to test above functions */
int main()
{
char S[] = "ABBDCACB";
int n = strlen(S);
cout << "The length of the Longest Palindromic Subsequence is "<< longestpalindromicsubsequence(S, 0, n1);
return 0;
}
Output:
The length of the Longest Palindromic Subsequence is 5
Approach 2: (Dynamic Programming)
This approach is efficient. Since there exists the optimal overlapping property, we can comfortably implement the Dynamic Programming Approach.
The Main Difference between the Recursion and Dynamic Programming Approach is
In the dynamic programming approach, we will not revisit the computed subroutine, instead, we will save all the computed values in an array and if we encounter the same recursive call to be computed again and again, we will simply make use of the functional value from the table. This approach is called Memoization.
Explanation of Memoization with an example
By Looking at the Figure of recursive calls, we see that while solving the recursive calls (1,5) and (0,4), we get (1,2) as a common recursive call to be computed again and again, so this may consume much more time, to avoid this time consuming, we simply store the value of (1,2) in an array or dictionary. So whenever we again require this value to be computed, we will simply reuse it from the stored array. In this way, we can save a huge amount of time, and we can even reduce the complexity of any algorithm respectively, this is called Dynamic Programming.
Dynamic Programming Algorithm
The Complete Algorithm is the same as the recursive one, and one extra functionality added to this is we will declare an extra key functionality to store precomputed values.
The complexity of Dynamic programming:
 Time Complexity : O(N^2)
 Space Complexity: O(N^2)
Where N is the length of the Input string.
Note : One thing that is to be kept in mind is that we should define the base case properly else, it may result in Recursion Depth Exceeded the exception.
Python Version Of Dynamic programming
# definition function longestpalandromicstring
def longestpalandromicstring(S, i, j,array):
# Base case
if i > j: # if the i pointer exceeds j pointer then we return 0
return 0
# If the two pointers are equal means, one unique character is present
if i == j:
return 1 # then we return 1
# declaring the key to store the computation calls
key = (i, j)
# we will check the key, before its computation into the array
if key not in array: # if it is not present then only we will start the recursion function
if S[i] == S[j]: # if its matches
array[key] = longestpalandromicstring(S, i + 1, j  1,array) + 2
else:
''' Consider a situation where the first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
We get the maximum value of the string as stated below:
Deleting the first character and apply the recursion for the remaining entire string S[i+1,j]
Deleting the last character and apply the recursion for the remaining entire string S[i,j1]
'''
array[key] = max(longestpalandromicstring(S, i, j  1, array),
longestpalandromicstring(S, i + 1, j, array))
# Return the subproblem solution from the dictionary
return array[key]
if __name__ == '__main__':
S = "ABBDCACB"
n = len(S)
# Create a dictionary to store solutions to subproblems
array = {}
print("The maximum longest palindromic subsequence is",
longestpalandromicstring(S, 0, n  1, array))
Output:
The maximum longest palindromic subsequence is 5
Java Version using Dynamic Programming
import java.util.HashMap;
import java.util.Map;
// defining the main class
public class Main
{
public static int longestPalindromestring(String S, int i, int j,
Map<String, Integer> map) // defining the longest palindromic string function
{// additionally we also declare a hashmap to map the precomputed elements
// Base case
if (i > j) { // if i pointer exceeds the j pointer
return 0; // we return 0
}
// If the string `S`contains only one unique character, it is a palindrome
if (i == j) {
return 1; // we return 1 since a palindrome is found
}
// we will now built the unique key to map the elements
String key = i + "" + j;
// for the first time store every precomputed value in the map and check for each recursive call
if (!map.containsKey(key)) // whether it contains the value or not
{
/* If the last character of the string is the same as the first character,
include the first and last characters in palindrome and recur
for the remaining substring `X[i+1, j1]` */
if (S.charAt(i) == S.charAt(j)) { // if the palindrome is detected, then increment the value by 2
map.put(key, longestPalindromestring(S, i + 1, j  1, map )+ 2);
}
else {
/* Consider a situation where the first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
We get the maximum value of the string as stated below:
Deleting the first character and apply the recursion for the remaining entire string S[i+1,j]
Deleting the last character and apply the recursion for the remaining entire string S[i,j1]
*/
map.put(key, Integer.max(longestPalindromestring(S, i, j  1, map), // simply choose the max value
longestPalindromestring(S, i + 1, j, map)));
}
}
// Return the precomputed subroutine
return map.get(key);
}
public static void main(String[] args)
{
String S = "ABBDCACB";
int n = S.length();
// Create a map to store the precomputed solutions
Map<String, Integer> array = new HashMap<>();
System.out.print("The maximum longest palindromic subsequence is " +
longestPalindromestring(S, 0, n  1, array));
}
}
Output :
The maximum longest palindromic subsequence is 5
C++ Version Using Dynamic Programming
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// defining the function to find the maximum longest palindrome subsequence
int longestPalindromestring(string S, int i, int j, auto &map)
{
// Base condition
if (i > j) { // if i pointer exceeds j pointer
return 0; // we will return 0
}
// If the string string 'S' has only one character, then a palindrome is detected
if (i == j) {
return 1; // we will return 1
}
//we will built a key to store the precomputed values
string key = to_string(i) + "" + to_string(j);
// if you encounter the subroutine for the first time then solve it and store it in the map s we discussed in the above approach
if (map. find(key) == map. end())
{
// if the first and last character are equal, then we will add 2 and increment the i pointer and decrement the j pointer
if (S[i] == S[j])
{
map[key] = longestPalindromestring(S, i + 1, j  1, map) + 2;
}
else {
/* Consider a situation where the first character doesn't match the last character, then, in this scenario, we will return the maximum of the two values:
We get the maximum value of the string as stated below:
Deleting the first character and apply the recursion for the remaining entire string S[i+1,j]
Deleting the last character and apply the recursion for the remaining entire string S[i,j1]
*/
map[key] = max (longestPalindromestring(S, i, j  1, map), // we will simply pick the maximum value
longestPalindromestring(S, i + 1, j, map));
}
}
//return the subroutine recursive call
return map[key];
}
int main()
{
string S = "ABBDCACB";
int n = S.length();
// Create a map to store the subroutine
unordered_map<string, int> map;
cout << "The length of the longest palindromic subsequence is " <<longestPalindromestring(S, 0, n 1, map);
return 0;
}
Output:
The Maximum Longest Palindromic Subsequence is 5.
Now we will see how to trace and print the Longest Palindromic Subsequence of the given string.
Algorithm
Here, we'll look at how to print the longest palindromic subsequence. The Longest Common Subsequence (LCS) problem is similar to this one. We can solve this problem by using LCS as a subroutine. The LCSbased twostep solution is shown below. 1) Reverse the given sequence and save it in a new array called rev[0..n1]. 2) The given sequence's LCS and rev[] will be the palindromic series that is the longest. 3) Once we've located LCS, we can print it.
Below is the Approach
Python version Dynamic programming
# The LCS problem is implemented using dynamic programming.
# Returns the LCS length for STRING1[0..m1], STRING2[0..n1], and STRING2[0..n1].
def lcs(X, Y, m, n):
array = [[0 for x in range(n+1)] for x in range(m+1)]
#Construct the array [m+1][n+1] from the bottom up using the steps below.
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
array[i][j] = 0
elif string1[i1] == string2[j1]:
array[i][j] = array[i1][j1] + 1
else:
array[i][j] = max(array[i1][j], array[i][j1])
# To print LCS, use the code below.
index = array[m][n]
# To store the lcs string, construct a character list.
lcs = [""] * (index+1)
lcs[index] = ""
#Begin at the rightmostbottommost corner and
#store characters in lcs[] one by one.
j = n
while i > 0 and j > 0:
#If the current character in X[] and Y[] is the same, then the current character belongs to LCS.
if string1[i1] == string2[j1]:
lcs[index1] = string1[i1]
i=1
j=1
index=1
#If the values are not equal, find the larger of the two and proceed in the direction of the larger value.
elif array[i1][j] > array[i][j1]:
i=1
else:
j=1
print("LCS of " + string1 + " and " + string2 + " is " + "".join(lcs))
# Driver program
string1 = "ABBDCACB"
string2 = 'BCACDBBA' # reverse of string1
m = len(string1)
n = len(string2)
lcs(string1, string2, m, n)
Output:
LCS of ABBDCACB and BCACDBBA is BCACB
Java Version of Dynamic Programming
// defining the Function to print longest palindromic subsequence of string `string1[0…m1]` and `string2[0…n1]`
public class palindromicsubsequence {
/* LCS string1 and string2 are returned */
static String lcs(String string1, String string2) {
int m = string1.length();
int n = string2.length();
char X1[] = string1.toCharArray();
char Y1[] = string2.toCharArray();
int table[][] = new int[m + 1][n + 1];
/* Construct table[m+1][n+1] from the bottom up using the steps below. Table[i][j] includes the lengths of string1[0..i1] and string2[0..j1] LCS. */
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) { if (i == 0  j == 0) { table[i][j] = 0; } else if (X1[i  1] == Y1[j  1]) { table[i][j] = table[i  1][j  1] + 1; } else { table[i][j] = Math.max(table[i  1][j], table[i][j  1]); } } } // To print LCS, use the code below. int pointer = table[m][n]; // Make a String of index+1 length and fill it with it char[] lcstore = new char[pointer + 1]; // Begin at the rightmostbottommost / corner and store characters in lcstore[] one after the other. int i = m, j = n; while (i > 0 && j > 0) {
//If the current character in string1[] and string2 are the same, then the current character is part of the LCStore.
if (X1[i  1] == Y1[j  1]) {
// insert the character in result
lcstore[pointer  1] = X1[i  1];
i;
j;
// decrement the of i, j and pointer values
pointer;
} //If the two values are not equal, find the larger of the two and proceed in the direction of the larger / value.
else if (table[i  1][j] > table[i][j  1]) {
i;
} else {
j;
}
}
String answer = "";
for (int x = 0; x < lcstore.length; x++) { answer += lcstore[x]; } return answer; } // Returns str's longest palindromic subsequence. static String lps(String str2) { //Find the opposite of str. String rev = str2; rev = reverse(rev); // Return the LCS of str as well as its inverse. return lcs(str2, rev); } static String reverse(String str3) { String answer = ""; //toCharArray() converts a String to a character array. char[] try1 = str3.toCharArray(); for (int i = try1.length  1; i >= 0; i) {
answer += try1[i];
}
return answer;
}
/* Test driver programme for the above identified feature */
public static void main(String[] args) {
String str1 = "ABBDCACB";
System.out.println(lps(str1));
}
}
C++ Version Of Dynamic Programming
/* c++ program to trace the longest palindromic subsequence */
#include<bits/stdc++.h>
using namespace std;
/* Returns LCS of string1 and string2 */
string longestcommonsubsequence(string &string1, string &string2)
{
int m = string1.length();
int n = string2.length();
int table[m+1][n+1];
/* In the following steps, construct the table [m+1][n+1] in a bottomup fashion. It is worth noting that table[i][j] contains the length of LCS for strings1[0..i1] and string2[0..j1]. */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++) { if (i == 0  j == 0) table[i][j] = 0; else if (string1[i1] == string2[j1]) table[i][j] = table[i1][j1] + 1; else table[i][j] = max(table[i1][j], table[i][j1]); } } // The code below is used to print LCS. int index1 = table[m][n]; // Make a string of index+1 length and assign all zeros to string lcsequence(index+1, '0'); string longestcommonsubsequence(index1+1, '\0'); int i = m, j = n; while (i > 0 && j > 0)
{
// If current character in string1[] and string2 are same, then current character ti is said that,it is the part of LCS
if (string1[i1] == string2[j1])
{
// insert the current char into the result
longestcommonsubsequence[index11] = string1[i1];
i;
j;
// start reducing the values i,j,index
index1;
}
// if they are not same then find the largest of them
else if (table[i1][j] > table[i][j1])
i;
else
j;
}
return longestcommonsubsequence;
}
// this function returns the longest palindromic subsequence
string lps(string &str1)
{
// reverse of the given input string is found
string rev = str1;
reverse(rev.begin(), rev.end());
// we will now return the reverse of the string
return longestcommonsubsequence(str1, rev);
}
// Driver code
int main()
{
string str1 = "ABBDCACB";
cout << lps(str1);
return 0;
}
Conclusion

In the above article, we have learned the following basic things:
 What is a subsequence?
 What is an optimal substructure?
 What is the overlapping subproblem property?
 We have also learned about the detailed procedure to solve the Longest palindromic subsequence along with its path.
 We did so using the Naive Approach and the Dynamic Programming Approach.
We hope that you will now be able to solve this problem, as well as its variants, without any difficulty.
People are also reading:
 Depth First Search(DFS) DSA
 Merge Two Sorted Arrays inplace
 Queue Data Structure
 Print all subarrays with 0 sum
 Pattern Program in C
 Rearrange an array in maximum minimum form
 Longest subarray with sum as K
 Find whether an array is subset of another array
 Rod Cutting Problem – Dynamic Programming
 Print a given matrix in spiral form
 Program to Rotate an Array
Leave a Comment on this Post