## Longest Palindromic Subsequence

### What is the longest palindromic subsequence?

The **longest palindromic subsequence** is a string of characters that spells the same forward and backward.

Characters in a **subsequence** are not required to be in consecutive positions in the original string, unlike characters in a substring.

**Example**

Take string “ABBCDABBC”, for example. Then the longest palindromic subsequence in this string is “BBABB”.

A naive approach would be to find all possible palindromic subsequences in “ABBCDABBC”, and filter out the longest one.

Notice

However, this approach has exponential time complexity.

Dynamic Programming is a much easier approach. It’s an optimization technique in which complex problems are broken down into subproblems and solved only once for each subproblem.

## Dynamic Programming Solution

The solution to another related problem, the Longest Common Subsequence (LCS) problem, can be used to solve this one. The definition is as follows:

## The mathematical equation

To put all of the above into a mathematical equation, write:

Lets call the original sequence X=(x_1 x_2 \cdots x_m)X=(x

1

x

2

⋯x

m

) and reverse as Y=(y_1 y_2 \cdots y_n)Y=(y

1

y

2

⋯y

n

). The prefixes of XX are X_{1,2,\cdots,m}X

1,2,⋯,m

and the prefixes of YY are Y_{1,2,\cdots,n}Y

1,2,⋯,n

.

Let \mathit{LCS}(X_i,Y_j)LCS(X

i

,Y

j

) represent the set of longest common subsequence of prefixes X_iX

i

and Y_jY

j

. Then:

\small \mathit{LCS}(X_{i},Y_{j}) = \begin{cases} \emptyset & if \:i=0 \:or j=0, \ \mathit{LCS}(X_{i-1},Y_{j-1}) \hat {} x_{i} & if \: i,j>0 \: \& \: x_{i} = y_{j}\ \max \big{ \mathit{LCS}(X_{i},Y_{j-1}), \mathit{LCS}(X_{i-1},Y_{j})\big} & if \: i,j>0 \: \& \: x_{i} \ne y_{j} \end{cases}LCS(X

i

,Y

j

)=

⎩

⎪

⎨

⎪

⎧

∅

LCS(X

i−1

,Y

j−1

)

^

x

i

max{LCS(X

i

,Y

j−1

),LCS(X

i−1

,Y

j

)}

ifi=0orj=0,

ifi,j>0&x

i

=y

j

ifi,j>0&x

i

≠y

j

If the last characters match, then the sequence \mathit{LCS}(X_{i-1},Y_{j-1})LCS(X

i−1

,Y

j−1

) is extended by that matching character x_ix

i

. Otherwise, the best result from \mathit{LCS}(X_{i},Y_{j-1})LCS(X

i

,Y

j−1

) and \mathit{LCS}(X_{i-1},Y_{j})LCS(X

i−1

,Y

j

) is used.