Introduction to Palindromic Subsequence

A palindrome is a sequence of characters that spells the same forward and backward. A palindromic subsequence is a palindrome within a string. The elements in the subsequence are not required to be at consecutive positions in the original string.

If we take a string “BBABCBCAB”, there could be many palindromic subsequences of different lengths. Some of them are “BAB”, “BB”, “BCB”, “BCBCB”, “BABAB”, “ABCBA”, “BABCBAB” , and so on. We can also find the longest palindromic subsequence, which is “BABCBAB” in our case.

We can solve this problem using the solution to another similar problem—the Longest Common Subsequence (LCS) problem. The idea 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.

Mathematically, it can be written as:

Let’s call the original sequence $X=(x_1x_2x_3...x_m)$ and reverse as $Y=(y_1y_2y_3...y_n)$. The prefixes of $X$ are $X_{1,2,...,m}$ ...