Understanding the longest palindromic subsequence problem

When working with strings, we often care not just about contiguous segments but about characters that can be selected from anywhere within the string while preserving their relative order. One such challenge is to determine the longest sequence of characters that reads the same forward and backward, without requiring those characters to be adjacent.

This is known as the longest palindromic subsequence problem, where the objective is to find the length of the longest subsequence of the input string that reads the same forward and backward.

The longest palindromic subsequence problem is a classic dynamic programming problem with practical applications in computational biology for comparing DNA sequences, diff tools for identifying structural similarities, and data compression.

In this lesson, we will learn about the longest palindromic subsequence problem and how it can be solved efficiently using a dynamic programming solution.

The longest palindromic subsequence problem

Consider we are given a string s of length n. A subsequence is a sequence of characters derived from s by deleting zero or more characters without changing the relative order of the remaining characters.