Longest Palindromic Subsequence (LPS)
Given a string ‘S’, find the length of the Longest Palindromic Subsequence in it.
The Longest Palindromic Subsequence (LPS) is the problem of finding a maximum-length subsequence of a given string that is also a Palindrome.
Longest Palindromic Subsequence
Examples:
Input: S = “w3wiki”
Output: 5
Explanation: The longest palindromic subsequence we can get is of length 5. There are more than 1 palindromic subsequences of length 5, for example: EEKEE, EESEE, EEFEE, …etc.Input: S = “BBABCBCAB”
Output: 7
Explanation: As “BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.
Recursive solution to find the Longest Palindromic Subsequence (LPS):
The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence. This solution is exponential in terms of time complexity. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem and can efficiently be solved using Dynamic Programming.
Following is a general recursive solution with all cases handled.
- Case1: Every single character is a palindrome of length 1
- L(i, i) = 1 (for all indexes i in given sequence)
- Case2: If first and last characters are not same
- If (X[i] != X[j]) L(i, j) = max{L(i + 1, j), L(i, j – 1)}
- Case3: If there are only 2 characters and both are same
- Else if (j == i + 1) L(i, j) = 2
- Case4: If there are more than two characters, and first and last characters are same
- Else L(i, j) = L(i + 1, j – 1) + 2
Below is the implementation for the above approach:
// C++ program of above approach
#include <bits/stdc++.h>
using namespace std;
// A utility function to get max
// of two integers
int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest
// palindromic subsequence in seq
int lps(char* seq, int i, int j)
{
// Base Case 1: If there is
// only 1 character
if (i == j)
return 1;
// Base Case 2: If there are only 2
// characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps(seq, i + 1, j - 1) + 2;
// If the first and last characters
// do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
// Driver program to test above functions
int main()
{
char seq[] = "w3wiki";
int n = strlen(seq);
cout << "The length of the LPS is "
<< lps(seq, 0, n - 1);
return 0;
}
// C program of above approach
#include <stdio.h>
#include <string.h>
// A utility function to get max of two integers
int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic subsequence
// in seq
int lps(char* seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j)
return 1;
// Base Case 2: If there are only 2 characters and both
// are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps(seq, i + 1, j - 1) + 2;
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above functions */
int main()
{
char seq[] = "w3wiki";
int n = strlen(seq);
printf("The length of the LPS is %d",
lps(seq, 0, n - 1));
getchar();
return 0;
}
// Java program of above approach
import java.io.*;
import java.util.*;
class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char seq[], int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
public static void main(String[] args)
{
String seq = "w3wiki";
int n = seq.length();
System.out.printf("The length of the LPS is %d",
lps(seq.toCharArray(), 0, n - 1));
}
}
# Python 3 program of above approach
# A utility function to get max
# of two integers
def max(x, y):
if(x > y):
return x
return y
# Returns the length of the longest
# palindromic subsequence in seq
def lps(seq, i, j):
# Base Case 1: If there is
# only 1 character
if (i == j):
return 1
# Base Case 2: If there are only 2
# characters and both are same
if (seq[i] == seq[j] and i + 1 == j):
return 2
# If the first and last characters match
if (seq[i] == seq[j]):
return lps(seq, i + 1, j - 1) + 2
# If the first and last characters
# do not match
return max(lps(seq, i, j - 1),
lps(seq, i + 1, j))
# Driver Code
if __name__ == '__main__':
seq = "w3wiki"
n = len(seq)
print("The length of the LPS is",
lps(seq, 0, n - 1))
# This code contributed by Rajput-Ji
// C# program of the above approach
using System;
public class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char[] seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
public static void Main()
{
String seq = "w3wiki";
int n = seq.Length;
Console.Write("The length of the LPS is "
+ lps(seq.ToCharArray(), 0, n - 1));
}
}
// This code is contributed by Rajput-Ji
// A utility function to get max of two integers
function max(x, y)
{
return (x > y) ? x : y;
}
// Returns the length of the longest palindromic subsequence in seq
function lps(seq, i, j)
{
// Base Case 1: If there is only 1 character
if (i == j)
{
return 1;
}
// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
{
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j])
{
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
let seq = "w3wiki";
let n = seq.length;
console.log("The length of the LPS is ", lps(seq.split(""), 0, n - 1));
// This code is contributed by avanitrachhadiya2155
Output
The length of the LPS is 5
Time complexity: O(2n), where ‘n’ is the length of the input sequence.
Auxiliary Space: O(n2) as we are using a 2D array to store the solutions of the subproblems.
Using the Memoization Technique of Dynamic Programming:
The idea used here is to reverse the given input string and check the length of the longest common subsequence. That would be the answer for the longest palindromic subsequence.
Below is the implementation for the above approach:
// A Dynamic Programming based C++ program
// for LPS problem returns the length of
// the longest palindromic subsequence
// in seq
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
// Returns the length of the longest
// palindromic subsequence in seq
int lps(string& s1, string& s2, int n1, int n2)
{
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
}
else {
return dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
// Driver program to test above functions
int main()
{
string seq = "w3wiki";
int n = seq.size();
dp[n][n];
memset(dp, -1, sizeof(dp));
string s2 = seq;
reverse(s2.begin(), s2.end());
cout << "The length of the LPS is "
<< lps(s2, seq, n, n) << endl;
return 0;
}
// Java program of above approach
import java.io.*;
import java.util.*;
class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char seq[], int i, int j, int dp[][])
{
// Base Case 1: If there is only 1 character
if (i == j) {
return dp[i][j] = 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return dp[i][j] = 2;
}
// Avoid extra call for already calculated
// subproblems, Just return the saved ans from cache
if (dp[i][j] != -1) {
return dp[i][j];
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return dp[i][j]
= lps(seq, i + 1, j - 1, dp) + 2;
}
// If the first and last characters do not match
return dp[i][j] = max(lps(seq, i, j - 1, dp),
lps(seq, i + 1, j, dp));
}
/* Driver program to test above function */
public static void main(String[] args)
{
String seq = "w3wiki";
int n = seq.length();
int dp[][] = new int[n][n];
for (int[] arr : dp)
Arrays.fill(arr, -1);
System.out.printf(
"The length of the LPS is %d",
lps(seq.toCharArray(), 0, n - 1, dp));
}
}
// This code is contributed by gauravrajput1
# A Dynamic Programming based Python program for LPS problem
# Returns the length of the longest palindromic subsequence
# in seq
dp = [[-1 for i in range(1001)]for j in range(1001)]
# Returns the length of the longest palindromic subsequence
# in seq
def lps(s1, s2, n1, n2):
if (n1 == 0 or n2 == 0):
return 0
if (dp[n1][n2] != -1):
return dp[n1][n2]
if (s1[n1 - 1] == s2[n2 - 1]):
dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1)
return dp[n1][n2]
else:
dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1))
return dp[n1][n2]
# Driver program to test above functions
seq = "w3wiki"
n = len(seq)
s2 = seq
s2 = s2[::-1]
print(f"The length of the LPS is {lps(s2, seq, n, n)}")
# This code is contributed by shinjanpatra
// C# code to implement the approach
using System;
using System.Numerics;
using System.Collections.Generic;
public class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char[] seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
// Driver Code
public static void Main(string[] args)
{
string seq = "w3wiki";
int n = seq.Length;
Console.Write("The length of the LPS is "
+ lps(seq.ToCharArray(), 0, n - 1));
}
}
// This code is contributed by sanjoy_62.
// A Dynamic Programming based JavaScript program for LPS problem
// Returns the length of the longest palindromic subsequence
// in seq
let dp;
// Returns the length of the longest palindromic subsequence
// in seq
function lps(s1, s2, n1, n2)
{
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
}
else {
return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
/* Driver program to test above functions */
let seq = "w3wiki";
let n = seq.length;
dp = new Array(1001);
for(let i=0;i<1001;i++){
dp[i] = new Array(1001).fill(-1);
}
let s2 = seq;
s2 = s2.split('').reverse().join('');
console.log("The length of the LPS is " + lps(s2, seq, n, n),"</br>");
// This code is contributed by shinjanpatra
Output
The length of the LPS is 5
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Using the Tabulation technique of Dynamic programming to find LPS:
In the earlier sections, we discussed recursive and dynamic programming approaches with memoization for solving the Longest Palindromic Subsequence (LPS) problem. Now, we will shift our focus to the Bottom-up dynamic programming method.
Below is the implementation for the above approach:
// A Dynamic Programming based C++ program for LPS problem
// Returns the length of the longest palindromic subsequence
#include <algorithm>
#include <cstring> // for memset
#include <iostream>
#include <string>
using namespace std;
int longestPalinSubseq(string S)
{
string R = S;
reverse(R.begin(), R.end());
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int dp[S.length() + 1][R.length() + 1];
// Initialize dp array with zeros
memset(dp, 0, sizeof(dp));
// Filling up DP table based on conditions discussed
// in the above approach
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= R.length(); j++) {
if (S[i - 1] == R[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.length()][R.length()];
}
// Driver code
int main()
{
string s = "w3wiki";
cout << "The length of the LPS is "
<< longestPalinSubseq(s) << endl;
return 0;
}
// This code is contributed by akshitaguprzj3
// A Dynamic Programming based Java program for LPS problem
// Returns the length of the longest palindromic subsequence
import java.io.*;
import java.util.*;
class GFG {
public static int longestPalinSubseq(String S)
{
String R
= new StringBuilder(S).reverse().toString();
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int dp[][]
= new int[S.length() + 1][R.length() + 1];
// Filling up DP table based on conditions discussed
// in above approach
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= R.length(); j++) {
if (S.charAt(i - 1) == R.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i][j - 1],
dp[i - 1][j]);
}
}
// At the end DP table will contain the LPS
// So just return the length of LPS
return dp[S.length()][R.length()];
}
// Driver code
public static void main(String[] args)
{
String s = "w3wiki";
System.out.println("The length of the LPS is "
+ longestPalinSubseq(s));
}
}
def longestPalinSubseq(S):
R = S[::-1]
# dp[i][j] will store the length of the longest
# palindromic subsequence for the substring
# starting at index i and ending at index j
dp = [[0] * (len(R) + 1) for _ in range(len(S) + 1)]
# Filling up DP table based on conditions discussed
# in the above approach
for i in range(1, len(S) + 1):
for j in range(1, len(R) + 1):
if S[i - 1] == R[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
# At the end, DP table will contain the LPS
# So just return the length of LPS
return dp[len(S)][len(R)]
# Driver code
s = "w3wiki"
print("The length of the LPS is", longestPalinSubseq(s))
# This code is contributed by shivamgupta310570
using System;
public class GFG {
// Function to find the length of the longest
// palindromic subsequence
static int LongestPalinSubseq(string S)
{
char[] charArray = S.ToCharArray();
Array.Reverse(charArray);
string R = new string(charArray);
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int[, ] dp = new int[S.Length + 1, R.Length + 1];
// Initialize dp array with zeros
for (int i = 0; i <= S.Length; i++) {
for (int j = 0; j <= R.Length; j++) {
dp[i, j] = 0;
}
}
// Filling up DP table based on conditions discussed
// in the above approach
for (int i = 1; i <= S.Length; i++) {
for (int j = 1; j <= R.Length; j++) {
if (S[i - 1] == R[j - 1])
dp[i, j] = 1 + dp[i - 1, j - 1];
else
dp[i, j] = Math.Max(dp[i, j - 1],
dp[i - 1, j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.Length, R.Length];
}
// Driver code
public static void Main(string[] args)
{
string s = "w3wiki";
Console.WriteLine("The length of the LPS is "
+ LongestPalinSubseq(s));
}
}
// This code is contributed by shivamgupta310570
// A Dynamic Programming based C++ program for LPS problem
// Returns the length of the longest palindromic subsequence
function longestPalinSubseq(S)
{
let R = S.split('').reverse().join('');
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
// Initialize dp array with zeros
let dp = new Array(S.length + 1).fill(0).map(() => new Array(R.length + 1).fill(0));
// Filling up DP table based on conditions discussed
// in the above approach
for (let i = 1; i <= S.length; i++) {
for (let j = 1; j <= R.length; j++) {
if (S[i - 1] == R[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return dp[S.length][R.length];
}
// Driver code
let s = "w3wiki";
console.log("The length of the LPS is " + longestPalinSubseq(s));
Output
The length of the LPS is 5
Time Complexity : O(n2)
Auxiliary Space: O(n2), since we use a 2-D array.
Using Space Optimized method of Dynamic programming to find LPS:-
In the previous solution you can clearly see that the current row is depending upon previous row. Its mean we are working with only two rows at a time. So, we have created 2 rows and initialized with 0s. We are using vector this time because swapping array becomes easy in vectors. The main logic behind this solution is that we finds the solution of current row then swaps it with the previous one in every iteration until we comes to the end of our strings;
#include <bits/stdc++.h>
using namespace std;
int longestPalinSubseq(string S) {
string R = S;
reverse(R.begin(), R.end());
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
vector<int> curr(R.length() + 1, 0);
vector<int> prev(R.length() + 1, 0);
// Filling up DP table based on conditions discussed
// in the above approach
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= R.length(); j++) {
if (S[i - 1] == R[j - 1])
curr[j] = 1 + prev[j - 1];
else
curr[j] = max(curr[j - 1], prev[j]);
}
prev = curr;
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return curr[R.length()];
}
// Driver code
int main()
{
string s = "w3wiki";
cout << "The length of the LPS is "
<< longestPalinSubseq(s) << endl;
return 0;
}
import java.util.Arrays;
public class Main {
public static int longestPalinSubseq(String S) {
StringBuilder R = new StringBuilder(S);
R.reverse();
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
int[] curr = new int[R.length() + 1];
int[] prev = new int[R.length() + 1];
// Filling up DP table based on conditions discussed
// in the above approach
for (int i = 1; i <= S.length(); i++) {
for (int j = 1; j <= R.length(); j++) {
if (S.charAt(i - 1) == R.charAt(j - 1))
curr[j] = 1 + prev[j - 1];
else
curr[j] = Math.max(curr[j - 1], prev[j]);
}
prev = Arrays.copyOf(curr, curr.length);
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return curr[R.length()];
}
// Driver code
public static void main(String[] args) {
String s = "w3wiki";
System.out.println("The length of the LPS is " + longestPalinSubseq(s));
}
}
def longest_palindrome_subseq(s):
# Reverse the string
r = s[::-1]
# Initialize DP tables
curr = [0] * (len(r) + 1)
prev = [0] * (len(r) + 1)
# Fill DP table
for i in range(1, len(s) + 1):
for j in range(1, len(r) + 1):
if s[i - 1] == r[j - 1]:
curr[j] = 1 + prev[j - 1]
else:
curr[j] = max(curr[j - 1], prev[j])
prev = curr[:]
# Return the length of the longest palindromic subsequence
return curr[-1]
# Driver code
if __name__ == "__main__":
s = "w3wiki"
print("The length of the LPS is", longest_palindrome_subseq(s))
// Function to find the length of the longest palindromic subsequence
function longestPalinSubseq(S) {
let R = S.split('').reverse().join('');
// dp[i][j] will store the length of the longest
// palindromic subsequence for the substring
// starting at index i and ending at index j
let curr = new Array(R.length + 1).fill(0);
let prev = new Array(R.length + 1).fill(0);
// Filling up DP table based on conditions discussed
// in the above approach
for (let i = 1; i <= S.length; i++) {
for (let j = 1; j <= R.length; j++) {
if (S[i - 1] === R[j - 1]) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(curr[j - 1], prev[j]);
}
}
prev = [...curr];
}
// At the end, DP table will contain the LPS
// So just return the length of LPS
return curr[R.length];
}
// Driver code
function main() {
let s = "w3wiki";
console.log("The length of the LPS is " + longestPalinSubseq(s));
}
// Calling the main function
main();
Output
The length of the LPS is 5
Time Complexity: O(n2)
Auxiliary Space: O(n)
Contact Us