Longest Palindromic Subsequence (using Dynamic Programming)

Reading time: 20 minutes | Coding time: 10 minutes

The longest palindrome subsequence problem (LPS) is the problem to find the length of longest subsequence in a string that is a palindrome. This can be done using Dynamic Programming in O(N2) time.

Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. We will see two solutions:

one which is a naive solutionthe other is a dynamic programming approach where we will reduce the time comple...