# Longest Palindrome Subsequence

Look at another commonly asked coding question based on strings and dynamic programming.

## We'll cover the following

## Problem statement

**Given a sequence of characters, find the length of the longest palindromic subsequence in it.**

For example, if the given sequence is **BBABCBCAB**, the output should be **7** as **BABCBAB** is the longest
palindromic subsequence in it. A sequence is a palindromic sequence if that sequence reads the same backward as forwards, e.g. madam.

Note: For the given sequence

BBABCBCAB, subsequenceBBBBBandBBCBBare also palindromic subsequences, but these are not the longest.

## Solution: **Recursive approach**

The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence.

Let **X[0 … n-1]** be the input sequence of length **n** and **L(0, n-1)** be the length of the longest palindromic subsequence of **X[0…n-1]**.

If the last and first characters of **X** are the same, then **L(0, n-1) = L(1, n-2) + 2**. Otherwise, **L(0, n-1) = MAX (L(1, n-1), L(0, n-2))**.
So the recursive relation can be written as:

- Every single character is a palindrome of length 1
**L(i, i) = 1**for all indexes**i**in a given sequence. - If the first and last characters are not same
- If
**X[i] != X[j]**, then**L(i, j) = max{L(i + 1, j), L(i, j - 1)}**

- If
- If there are only 2 characters and both are the same
- Else if
**j == i + 1**, then**L(i, j) = 2**

- Else if
- If there are more than two characters, and the first and last characters are the same
- Else
**L(i, j) = L(i + 1, j - 1) + 2**.

- Else

Let’s move on to the implementation of this problem now.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.