Search⌘ K
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: Longest Palindromic Subsequence

Explore the dynamic programming solution to the Longest Palindromic Subsequence problem by leveraging the Longest Common Subsequence approach. Understand why the original string and its reverse are compared and analyze the time and space complexity. Learn the difference between palindrome subsequences and substrings and examine bottom-up dynamic programming methods to enhance palindrome detection.

We'll cover the following...

Solution: Using longest common subsequence function

Python 3.5
from lcs import LCS
# call longest common subsequence function as follows: 
#   LCS(str1, str2)
#   returns integer for length of the longest common subsequence in str1 and str2
def LPS(str):
    return LCS(str, str[::-1])
print(LPS("racercar"))

Explanation

That’s it. All the magic happens in the LCS function and we have already seen how that function works in the previous solution review. We have simply called the LCS function with the actual string str and its reversed form str[::-1]. Let’s see why this works.

We know that we wrote our LCS algorithm to compare characters from the start of the strings towards the end. In this case, we want to compare the same string starting from the opposite ends. One way to exploit our implementation of LCS is to simply pass it the original string and its reversed version.

Time and space complexity

Time taken in reversing a string is O(n), while we know that LCS has a time complexity of O(nm) given strings of sizes n and m. Since here we have two versions of the same string, they will have the same length, n. Thus, the time complexity would be O(n2^2). Similarly, the space complexity would also be O(n2^2 ...