Challenge: Longest Palindromic Subsequence
In this lesson, we will build on the problem from the last coding challenge to solve another interesting problem.
We'll cover the following
Problem statement
Given a string, find the length of the longest common palindromic subsequence in that string. Let’s first review what a palindrome is. A palindrome is a sequence that reads the same in either direction. For example, madam
is a famous palindromic string. If you read it from start to end or from end to start, it reads the same.
As we have seen in the last challenge, unlike substring, subsequence does not have to be contiguous. So, in a string, racer car
, we may not have any palindromic substring of length greater than one, but we have a few palindromic subsequences. For example, cec
, aceca
, or the longest of them all racecar
.
So, you need to find the length of the longest palindromic subsequence.
Input
Your algorithm will take a string of variable length as input.
str = "racercar"
Output
Your algorithm should return an integer value representing the length of the longest palindromic subsequence in the given string.
LPS("racercar") = 7
Coding challenge
This problem builds on the problem of the longest common subsequence we discussed in the last lesson. Try to think about how you can define this problem in terms of the longest common subsequence problem. We have provided the function to find the length of the longest common subsequence below. You may use this function in your solution. If you are able to figure out the relation of this problem with the longest common subsequence problem, it is a really easy problem. So, think carefully and then write the code. Best of luck!
Get hands-on with 1200+ tech skills courses.