Challenge: Longest Palindromic Subsequence

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!