Longest Palindrome Subsequence

Problem statement

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

For example, if the given sequence is BBABCBCAB, the output should be 7 as BABCBAB is the longest palindromic subsequence in it. A sequence is a palindromic sequence if that sequence reads the same backward as forwards, e.g. madam.

Note: For the given sequence BBABCBCAB, subsequence BBBBB and BBCBB are also palindromic subsequences, but these are not the longest.

Solution: Recursive approach

The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence.

Let X[0 … n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0…n-1].

If the last and first characters of X are the same, then L(0, n-1) = L(1, n-2) + 2. Otherwise, L(0, n-1) = MAX (L(1, n-1), L(0, n-2)). So the recursive relation can be written as:

• Every single character is a palindrome of length 1 L(i, i) = 1 for all indexes i in a given sequence.
• If the first and last characters are not same
  • If X[i] != X[j], then L(i, j) = max{L(i + 1, j), L(i, j - 1)}
• If there are only 2 characters and both are the same
  • Else if j == i + 1, then L(i, j) = 2
• If there are more than two characters, and the first and last characters are the same
  • Else L(i, j) = L(i + 1, j - 1) + 2.

Let’s move on to the implementation of this problem now.