Question

A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

$\mathit{A}\mathbf{,}\mathit{C}\mathbf{,}\mathit{G}\mathbf{,}\mathit{T}\mathbf{,}\mathit{G}\mathbf{,}\mathit{T}\mathbf{,}\mathit{C}\mathbf{,}\mathit{A}\mathbf{,}\mathit{A}\mathbf{,}\mathit{A}\mathbf{,}\mathit{A}\mathbf{,}\mathit{T}\mathbf{,}\mathit{C}\mathbf{,}\mathit{G}$

has many palindromic subsequences, including $\mathit{A}\mathbf{,}\mathit{C}\mathbf{,}\mathit{G}\mathbf{,}\mathit{C}\mathbf{,}\mathit{A}$and $\mathit{A}\mathbf{,}\mathit{A}\mathbf{,}\mathit{A}\mathbf{,}\mathit{A}$(on the other hand, the subsequence $\mathit{A}\mathbf{,}\mathit{C}\mathbf{,}\mathit{T}$is not palindromic). Devise an algorithm that takes a sequence $\mathit{X}\left[1...n\right]$and returns the (length of the) longest palindromic subsequence. Its running time should be$\mathbf{0}\left(n^2\right)$.

Short answer

We say a string$x\left[i....j\right]$is a palindrome if$x\left[i\right]=x\left[j\right]\mathrm{or}x\left[i+1\right]=x\left[j-1\right]$

Since we need to find the Longest Palindromic Subsequence, for this we will be using dynamic programming approach.

Step-by-step solution

Approach

Here we will first define our sub-problem which would serve as recursive relation, and then we would be calling the sub-problem recursively.

In this question, following two possibilities are:

• If the first and last character of a string are same, include the first and last character in the palindrome and then in same corresponding order, recursively check for other remaining character.

For instance, if a string is$x\left[i....j\right]$, then check$x\left[i\right]=x\left[j\right],x\left[i+1\right]=x\left[j-1\right]$and so on.

• If the first character of the string not matches with the last character, then go back to the values we got from by:
• Either removing first character from $x\left[i....j\right]$.
• Or removing the last character from $x\left[i....j\right]$.

Recursive Relation

$\mathit{S}\left(i,j\right)=\left\{\begin{array}{c}\mathbf{1}\mathbf{}\mathbf{;}\mathbf{}\mathbf{if}\mathbf{}\mathbf{i}\mathbf{=}\mathbf{j}\\ \mathbf{2}\mathbf{+}\mathbf{S}\left(i+1,j-2\right)\mathbf{}\mathbf{;}\mathbf{}\mathbf{if}\mathbf{}\mathbf{i}<jandx\left[i\right]\mathbf{}\mathbf{=}\mathbf{x}\left[j\right]\\ \mathbf{max}\left\{S\left(i,j-1\right),S\left(i+1,j\right)\right\};\mathbf{otherwise}\end{array}\right.$

Where $S\left(i,j\right)$define the length of the palindrome.

Implementation of Algorithm

$$\begin{gathered} for\left(i=2ton+1\right) \\ S\left(i,i-1\right)=0 \\ for\left(i=1ton-1\right) \\ S\left(i,i\right)=1 \\ for\left(m=1ton-1\right) \\ for\left(i=nto\left(n-m\right)\right) \\ j=i+m \\ if\left(x\left[i\right]=x\left[j\right]\right) \\ S\left[i,j\right]=2+S\left(i+1,j-1\right) \\ else \\ S\left[i,j\right]=max\left\{S\left(i,j-1\right),S\left(i+1,j\right)\right\} \\ returnS\left(1,n\right) \end{gathered}$$

This solution will return us the longest palindrome in the string $x\left[i....j\right]$.