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.
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.
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.
Contact Us