# Longest Palindromic Subsequence using Dynamic Programming

The Longest Palindromic Subsequence (LPS) problem is the problem of finding the longest subsequences of a string that is also a palindrome.

The problem differs from problem of finding common substrings. Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

For example, Consider the sequence ABBDCACB

The length of Longest Palindromic Subsequence is 5
The Longest Palindromic Subsequence is BCACB

The idea is to use recursion to solve this problem. The idea is compare the last character of the string X[i..j] with its first character. There are two possibilities –

1. If the last character of the string is same as the first character, we include first and last characters in palindrome and recurse for the remaining substring X[i+1, j-1]

2. If last character of string is different from the first character, we return maximum of the two values we get by
• removing the last character and recursing for the remaining substring X[i, j-1]
• removing the first character and recursing for the remaining substring X[i+1, j]

This yields the below recursive relation to find the length of longest repeated Subsequence of a sequence X.

| 1                                      (if i = j)
LPS[i..j] = | LPS[i+1..j-1] + 2                      (if X[i] = X[j])
| max (LPS[i+1..j], LPS[i..j-1])         (if X[i] != X[j])

Below solution finds the length of longest repeated Subsequence of sequence X recursively by using above relations.

## C++

Output:

The length of Longest Palindromic Subsequence is 5

## Java

Output:

The length of Longest Palindromic Subsequence is 5

The worst case time complexity of above solution is exponential O(2n) and auxiliary space used by the program is O(1). The worst case happens when there is no repeated character present in X (i.e. LPS length is 1) and each recursive call will end up in two recursive calls.

The LPS problem has an optimal substructure and also exhibits overlapping subproblems. Let us consider recursion tree for sequence of length 6 having all distinct characters (say ABCDEF) whose LPS length is 1.

As we can see, the same sub-problems (highlighted in same color) are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. This method is illustrated below in C++ and Java –

## C++

Output:

The length of Longest Palindromic Subsequence is 5

## Java

Output:

The length of Longest Palindromic Subsequence is 5

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

Above solutions only find the length of Longest Palindromic Subsequence but do not print the Longest Palindromic Subsequence itself.

##### How can we print Longest Palindromic Subsequence?

The Longest Palindromic Subsequence problem is classic variation of Longest Common Subsequence (LCS) problem. The idea is to find LCS of given string with its reverse i.e. call LCS(X, reverse(X)) and the Longest Common Subsequence will be Longest Palindromic Subsequence.

## Java

Output:

The length of Longest Palindromic Subsequence is 5
The Longest Palindromic Subsequence is BCACB

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

Exercise: Write bottom-up solution for above recursive top-down version.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Xenial

Can you also post the longest palindromic substring solution?

Guest

I may be missing something here, but it looks like this solution has a bug or it was run on a different input:

ABBDCACB does not contain the string “BCACB”. The longest palindrome I see is “CAC”, which would make the answer 3.

Guest
Vishwajeet

Can You also post the application of this type of questions with real life problems..
It will help a lot in visualisation