Longest Palindromic Subsequences

noreply@blogger.com (Vikas Singh) — Sun, 23 Dec 2018 15:15:00 +0000

Objective - Given a sequence, find the length of the longest palindromic subsequence in it.

We will solve this using Dynamic Programming.
Dynamic Programming breaks a problem into subproblems.
It then solves every subsubproblem just once and then saves its answer in a table
It give complete solution of problem by combining solutions of subproblems

There can be many other palindromic subsequence but we have to find longest palindromic subsequence.

Approach:

Let input string is S[0..8] = DPAQLRASD and LPS[0..8] be length of length of longest palindromic subsequence. Length(S) = 9 . Sub strings of S can be -

Substrings of length 1 - D, P, A, Q, L, R, A, S, D
Substrings of length 2 - DP, PA, AQ, QL, LR, RA, AS, SD
...
...
Substring of length 9 - DPAQLRASD

Now consider the substring S[1..7] = PAQLRAS

So, If we have solution of sub problem for string S[1..7] = PAQLRAS (Substring of length 7) we can easily get the solution for string S[0..8] = DPAQLRASD

Lets say LPS[1..7] is n then LPS[0..8] = n +2

But what if x and x are not same?

Consider the input string S[0..8] = "PDQALRATD"

So if we know the solution of subproblem for string S[0..7] = PDAQLRAT (substring of length 8)

and for string[1..8] = DAQLRATD (substring of length 8) then we easily calculate the the solution for our input string S[0..8] which will be MAX(LPS[0..7], LPS[1..8]).

We can see that for solving the problem for a string of length 9 if we have to solve the the problem for substrings of length 8 and substrings of length 7. By using the solution smaller subproblems we can get solution of our problem.

So we can solve this problem in bottom up manner starting for substring of length 1 and ending with substring of length 9

It is obvious that for substring of length 1 ( P,D,A,Q,L,R,A,T,D) length of LPS will be 1

// A Dynamic Programming based Java

class LPS
{

// 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(String seq)
{
int n = seq.length();
int i, j, cl;
// Create a table to store results of subproblems
int L[][] = new int[n][n];

// Strings of length 1 are palindrome of lentgh 1
for (i = 0; i < n; i++)
L[i][i] = 1;

// Build the table. Note that the lower
// diagonal values of table are
// useless and not filled in the process.
.
// cl is length of substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (seq.charAt(i) == seq.charAt(j) && cl == 2)
L[i][j] = 2;
else if (seq.charAt(i) == seq.charAt(j))
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}

return L[0][n-1];
}

public static void main(String args[])
{
String seq = "DPAQLRASD";
int n = seq.length();
System.out.println("The lnegth of the lps is "+ lps(seq));
}
}

Make It So Easy

Longest Palindromic Subsequences