Longest Palindromic Subsequence

algorithm
dynamic-programming
longest-palindromic-subsequenc
(Team) #1

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/
0 Likes