Question

(General guidance: in responding to the following four questions, do not simply provide pseudo-code. Rather explain the main insight in such a way that an experienced programmer could devise an implementation of the algorithm on the basis of your explanation. Indeed, pseudo-code may not be necessary at all.)

Give an algorithm that takes as input a string and returns the length of its longest palindromic subsequence.

Answer 1

Solution:

The naive solution would be to generate all possible subsequence string with the given string and then checking wether that subsequence string is palindrome or not.If it is a palindrome then we should compare it's length with the longest palindromic string encountered till now and update the maximum length if the length of current subsequence is greater than previous longest palindromic subsequence ecountered.

So, if the length of the string is n then there are 2ⁿ subsequences and we have to check them all. Therefore using the naive approach time compexity will be exponentail.

Let arr[0..n-1] be the input sequence of length n and len(0, n-1) be the length of the longest palindromic subsequence of arr[0..n-1].

If first and last characters of arr are same

len(0, n-1) = len(1, n-2) + 2.
Else

L(0, n-1) = MAX (len(1, n-1), len(0, n-2)).

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

(Handling all cases of the problem)

// Every single character is a palindrome of length 1

len(i, i) = 1 for all indexes i in given sequence   

// IF first and last characters are not same

If (arr[i] != arr[j]) len(i, j) = max{len(i + 1, j), len(i, j - 1)}

// If there are only 2 characters and both are same

Else if (j == i + 1) len(i, j) = 2

// If there are more than two characters, and first and last

// characters are same

Else len(i, j) = len(i + 1, j - 1) + 2

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

We can further optimise the solution using Dynamic Programming approach as there are many repetitive recursive call which are made. Recomputations of same subproblems can be avoided by constructing a temporary array len[][] in a bottom-up manner.