5 Best Ways to Find the Length of Longest Palindromic Subsequence Using Python

Rate this post

πŸ’‘ Problem Formulation: A palindromic subsequence is a sequence of characters that reads the same backward as forward. The challenge in this article is to determine the length of the longest palindromic subsequence from a given string input. For example, if the input is "BBABCBCAB", the longest palindromic subsequence is "BABCBAB" or "BBCABB", and its length is 7.

Method 1: Recursive Approach

Recursion allows for a straightforward but less efficient method of computing the length of the longest palindromic subsequence. It works by comparing the first and last characters of the string. If they match, it recursively checks the subsequence inside. If they don’t, it decides the longer length between removing either the first or the last character and processes it recursively.

Here’s an example:

def lps(seq, i, j):
    if i == j:
        return 1
    if seq[i] == seq[j] and i + 1 == j:
        return 2
    if seq[i] == seq[j]:
        return lps(seq, i+1, j-1) + 2
    return max(lps(seq, i, j-1), lps(seq, i+1, j))

sequence = "BBABCBCAB"
print("Length of the LPS is", lps(sequence, 0, len(sequence)-1))

Output: Length of the LPS is 7

This recursive approach visually represents the core idea behind finding palindromic subsequences by checking matching characters and analyzing the subsequence inside the current compared pair. However, this method is not efficient for longer strings due to its exponential time complexity.

Method 2: Dynamic Programming

Using dynamic programming, a two-dimensional table can be created to store lengths of longest palindromic subsequences for subproblems, avoiding recalculation and thus reducing overall complexity to polynomial time. After filling the table, the length of the longest palindromic subsequence can be read directly from the table.

Here’s an example:

def lps(seq):
    n = len(seq)
    L = [[0 for x in range(n)] for x in range(n)]

    for i in range(n):
        L[i][i] = 1

    for cl in range(2, n+1):
        for i in range(n-cl+1):
            j = i+cl-1
            if seq[i] == seq[j] and cl == 2:
                L[i][j] = 2
            elif seq[i] == seq[j]:
                L[i][j] = L[i+1][j-1] + 2
            else:
                L[i][j] = max(L[i][j-1], L[i+1][j])

    return L[0][n-1]

sequence = "BBABCBCAB"
print("Length of the LPS is", lps(sequence))

Output: Length of the LPS is 7

In this approach, we fill the table in a bottom-up manner. The table has the property that L[i][j] contains the length of the longest palindromic subsequence of the substring starting at index i and ending at index j. Dynamic programming greatly increases efficiency compared to pure recursion.

Method 3: Memoization (Top-Down Dynamic Programming)

Memoization is a technique wherein we store the results of expensive function calls and return the cached result when the same inputs occur again. This approach is a hybrid of recursion and dynamic programming, often referred to as top-down dynamic programming.

Here’s an example:

def lps(seq, i, j, memo):
    if memo[i][j] != -1:
        return memo[i][j]

    if i == j:
        memo[i][j] = 1
    elif seq[i] == seq[j] and i+1 == j:
        memo[i][j] = 2
    elif seq[i] == seq[j]:
        memo[i][j] = lps(seq, i+1, j-1, memo) + 2
    else:
        memo[i][j] = max(lps(seq, i, j-1, memo), lps(seq, i+1, j, memo))
    
    return memo[i][j]

sequence = "BBABCBCAB"
memo = [[-1 for i in range(len(sequence))] for j in range(len(sequence))]
print("Length of the LPS is", lps(sequence, 0, len(sequence)-1, memo))

Output: Length of the LPS is 7

This memoization approach leverages the benefits of recursion for code simplicity while circumventing its inefficiencies by caching intermediate results.

Method 4: Space Optimized Dynamic Programming

Space-optimized dynamic programming improves upon the table-filling algorithm of dynamic programming by using only two arrays instead of a full two-dimensional matrix. It relies on the fact that to compute L[i][j], we only need to access values from the previous row.

Here’s an example:

def lps(seq):
    n = len(seq)
    L = [0] * n
    for i in range(n-1, -1, -1):
        back_up = 0
        for j in range(i, n):
            if j == i:
                L[j] = 1
            elif seq[i] == seq[j]:
                tmp = L[j]
                L[j] = back_up + 2
                back_up = tmp
            else:
                back_up = L[j]
                L[j] = max(L[j-1], L[j])
    return L[n-1]

sequence = "BBABCBCAB"
print("Length of the LPS is", lps(sequence))

Output: Length of the LPS is 7

This method reduces space complexity significantly while maintaining the polynomial time complexity of the dynamic programming approach. It’s particularly useful when memory usage is a concern.

Bonus One-Liner Method 5: Using Built-in Python Features

Though perhaps not as educational, Python’s powerful features allow for a single line solution by utilizing the built-in functools.lru_cache to quickly implement memoization.

Here’s an example:

from functools import lru_cache

@lru_cache(maxsize=None)
def lps(s):
    if not s:
        return 0
    if len(s) == 1:
        return 1
    if s[0] == s[-1]:
        return 2 + lps(s[1:-1])
    return max(lps(s[:-1]), lps(s[1:]))

sequence = "BBABCBCAB"
print("Length of the LPS is", lps(sequence))

Output: Length of the LPS is 7

This one-liner showcases Python’s ability to compress complex algorithms into concise and readable code, leveraging decorators and caching for efficient performance with minimal code written by the developer.

Summary/Discussion

  • Method 1: Recursive Approach. Straightforward, Conceptually simple. Not efficient for large inputs.
  • Method 2: Dynamic Programming. Efficient for larger inputs, Outputs computed in polynomial time. Requires substantial memory for large strings.
  • Method 3: Memoization. Code simplicity of recursion with optimality of dynamic programming. Reduced but still significant memory usage.
  • Method 4: Space Optimized Dynamic Programming. Reduces memory usage, Maintains polynomial time complexity. Slightly more complex logic than a plain dynamic programming approach.
  • Bonus Method 5: Using Built-in Python Features. Concise, Utilizes Python’s full capacity. Less didactic for understanding the algorithm’s mechanics.