Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Longest Palindromic Subsequence

Objec­tive: Given a string, find a longest palin­dromic sub­se­quence in it.

What is Longest Palin­dromic Sub­se­quence: A longest palin­dromic sub­se­quence is a sequence that appears in the same rel­a­tive order, but not nec­es­sar­ily contiguous(not sub­string) and palin­drome in nature( means the sub­se­quence will read same from the front and back.

Example:

String A = " AABCDEBAZ";

Longest Palindromic subsequence: ABCBA or ABDBA or ABEBA

There are many subsequences can be found which are palindrome like, AA, BCB, ABA, BB etc but we need to find the one with the maximum length.
Longest Palindromic Subsequence Example

Approach:

Recur­sion:

Check every sub­se­quence of in a given string, which means every char­ac­ter as two options, whether it will be included in the sub­se­quence or it will be excluded. If we do it by recur­sion which means all the sub prob­lems will be solved repeat­edly that means Time Com­plex­ity will be O(2n).

We can do it bet­ter by solv­ing this prob­lem using Dynamic Pro­gram­ming.

Dynamic Pro­gram­ming:

Opti­mal Substructure:

Given Sequence A[0….n-1]

LPS[0….n-1] be the longest palin­dromic sub­se­quence of the given sequence.

Check the first and the last char­ac­ters of the sequence. Now there are two pos­si­bil­i­ties, either both the char­ac­ters same or dis­tinct. We will have to han­dle both the case.

  • If both char­ac­ters are same, add 2 to the result and remove both the char­ac­ters and solve the prob­lem for the remain­ing subsequence .
Longest Palindromic Subsequence - 1

Longest Palin­dromic Sub­se­quence — 1

  • If both char­ac­ters are dif­fer­ent, then solve the prob­lem twice, ignore the first char­ac­ter (keep the last character)and solve the remain­ing sub­se­quence and then ignore the last char­ac­ter (keep the first char­ac­ter) and solve it and pick the best out of two results.

Longest Palindromic Subsequence - 2

 

Over­lap­ping Sub­prob­lems:

Say given input string: ABCDE

If we solve it recur­sively, look at the recur­sion tree, we will be solv­ing the sub-problems repeatedly.

Longest Palindromic Subsequence - Overlapping Subproblems

Longest Palin­dromic Sub­se­quence — Over­lap­ping Subproblems

So while using the dynamic pro­gram­ming, we will solve it in bottom-up man­ner and store the results of sub-problems once we solve them for future ref­er­ence. See the code for the bet­ter explanation

Recur­sive Equations:

LPS[i, i] = 1 Every sin­gle char­ac­ter is a palin­drome by itself of length 1
LPS[i, j] = 2 if j=i+1, sequence has only 2 characters
LPS[i, j] = 2 + LPS[i-1, j-1] If first and last char­ac­ters are same
LPS[i, j] = MAX(LPS[i+1,j], LPS[i, j-1]) If first and last char­ac­ters are not same

 

Code:

Output: 

1 2 2 2 2 2 3 5 5
0 1 1 1 1 1 3 5 5
0 0 1 1 1 1 3 3 3
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1

You may also like...

  • Nguyen Hoang Nam

    Hello, I’ve another way to solve this prob­lem, but i don’t know it can be called Dynamic Pro­gram­ming or not. Here is my code in java: https://gist.github.com/nhnpro/fd6f3c4052658ecca34155d7c46382f8

    Thanks

  • Jon Roet­man

    Unless I’m miss­ing some­thing here, isn’t the example’s (AABCDEBAZ) longest palin­dromic sub­se­quence “AA”, which is 2? It seems the out­put indi­cates 5.…

  • Prashant Kumar

    thnks !! great explanation

  • robin­frm­rome

    Hi,

    In the above code. Con­sider the fol­low­ing scenario

    String: abca
    i = 0
    j = 3

    Then the result would 2 which is incor­rect. It should rather be 1.

    Please explain/correct me if I am wrong.

    Thank You.

    • tuto­ri­al­hori­zon

      Hello Robin, I think you are con­fus­ing this prob­lem with longest palin­dromic sub­string, its a sub sequence. so answer to your exam­ple would be 3 not 1. and longest sequence would be either ‘aba’ or ‘aca’