Best Programming Master

In this article, we will look at yet another interesting problem popular in coding interviews. The problem states that Given a String we have to Find the Longest Palindromic Subsequence present in the String. We need to find only the Length of such subsequence. We will discuss various approaches related to our problem and analyze the time and space complexities. By Subsequence , we mean a sequence of string characters not necessarily contiguous but they have to preserve their relative ordering. For Example, for the String : ABBHJ, AHJ is a subsequence of the string, because characters follow the order and each of them are present in the String. Now, we need to find a Palindromic Subsequence. E.g. For String, CBAFAB, BAAB and BAFAB are subsequences of the string and are palindrome. But Subsequence BAFAB is the longest among them with length 5. Note: If a sequence of characters is contiguous it is a Substring. A substring is also a Subsequence. Let us look at different approaches to