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

LEAVE A REPLY

Please enter your comment!
Please enter your name here