Dynamic Programming – Longest Palindromic Sequence

Source Code for Longest Palindromic Subsequence

You can download the complete code from the github repository for techieme.

Building the DP table

Backtracking to find one palindrome.

Analysis

Building the DP Table
It takes O(N2) running time, because of the two loops there. Each running till the end of the given string.
The space is O(N2) as well. But you can see that we really do not need the complete matrix. Also, if we just need to learn the length then we need do not even need the matrix, we can just use four variables at a time. So, that can be considered as constant space O(1). However, that would need some tweaks.

Why do I say constant space?
For calculating the value of any given cell (i, j), we only need the values of cell(i+1,j-1) or cell(i+1,j) and cell(i,j-1). Hence just four cells at a time.

For backtracking
Backtracking requires one loop, hence the running time would be O(N) but the space complexity changes to O(N2) as we need the complete matrix stored.

Conclusion

There can be more than one longest palindromic sub sequence. The back tracking code has to be wisely modified to find all possible sequences. This currently finds just one such sequence.

Another similar question is to find the longest palindromic sub string, which ideally is considered to take O(N2) or O(2N) time. We will try to solve it in linear time using Manacher’s Algorithm.

Don’t forget to subscribe to TechieMe to get updates on latest posts.