# Longest Palindromic Subsequence

0
850

## 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:

• Reverse the given sequence. Let’s call the original sequence original. Let’s call the reversed sequence reverse.
• Use the LCS algorithm to find the longest common subsequence between original and reverse. Let LCS(original, reverse) be a function that returns the longest common subsequence between the pair of strings.
• The answer from LCS will in fact be the longest palindromic subsequence.

## 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.

Longest palindromic substring – Wikipedia