Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview in C++

Introduction to Palindromic Subsequence

Explore the concept of palindromic subsequences and learn to solve related dynamic programming problems using the longest common subsequence method. Understand how to find, count, and work with palindromic subsequences, and apply these techniques to optimize string-related challenges in coding interviews.

We'll cover the following...

Overview

In this pattern, we will be discussing 5 problems related to this pattern. The following diagram shows an overview of this pattern.

Problems explored in Palindromic Subsequence pattern

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”, ...

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=(x1x2x3...xm)X=(x_1x_2x_3...x_m) ...