The longest palindrome subsequence problem (LPS) is the problem to find longest subsequences of a string that is also a palindrome. Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. We will see two solutions one which is a naive solution and the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N^2).
Read this article to understand solving Longest Palindromic Subsequence using Dynamic programming in depth
Have a doubt or thought? Join the discussion now
This is a companion discussion topic for the original entry at http://iq.opengenus.org/longest-palindromic-subsequence/