💡 Problem Formulation: Given a string, the objective is to determine the length of the longest palindromic subsequence it can form. This palindromic property means the sequence reads the same forward and backward. For example, given the input ‘character’, a possible palindromic subsequence is ‘carac’, and its length, which is 5, is what our program should return.
Method 1: Dynamic Programming
Dyamic programming is an optimization approach where complex problems are broken down into simpler subproblems. It solves each subproblem just once and stores the results in a memory-based data structure (array, map, etc.). For finding the longest palindromic subsequence, we construct a 2D array where each cell represents the maximum palindrome length between specific indices of the string.
Here’s an example:
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = 2 + dp[i+1][j-1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence("character"))
Output: 5
This code initializes a square matrix (dp) with zeroes, then populates it by iteratively increasing subsequence lengths, checking for palindromic sequences, and storing the maximum length found. It uses the fact that a palindrome remains a palindrome if the same character is added at both its start and end.
Method 2: Recursion with Memoization
Recursion is the approach of solving a problem by breaking it down into simpler instances of the same problem. Memoization enhances recursion by storing the results of expensive function calls to avoid redundant calculations. This method applies these concepts by recursively exploring all subsequences and memorizing the lengths of palindromic ones.
Here’s an example:
def memoize(func):
memo = {}
def helper(x, y, s):
if (x, y) not in memo:
memo[(x, y)] = func(x, y, s)
return memo[(x, y)]
return helper
@memoize
def lps(x, y, s):
if x == y:
return 1
if x > y:
return 0
if s[x] == s[y]:
return 2 + lps(x+1, y-1, s)
return max(lps(x+1, y, s), lps(x, y-1, s))
string = "character"
print(lps(0, len(string)-1, string))
Output: 5
The helper function ‘lps’ is decorated with the ‘memoize’ decorator, which stores the length of the longest palindromic subsequence in a dictionary using the starting and ending indices as keys. The recursion explores all possible subsequences, and the memoization ensures that each unique pair of indices is solved only once.
Method 3: Using the Longest Common Subsequence
The longest common subsequence (LCS) approach finds the longest subsequence common to two strings. By comparing the string with its reverse, we can determine the longest palindromic subsequence using LCS, as this common subsequence will also be palindromic.
Here’s an example:
def longest_common_subsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
string = "character"
print(longest_common_subsequence(string, string[::-1]))
Output: 5
This LCS method first constructs a 2D array ‘dp’ that is used to store the lengths of common subsequences found during the iteration over both the original string and its reversed version. By populating this matrix, we can find the length of the longest common subsequence, which in the case of a string compared with its reverse, is the longest palindromic subsequence.
Method 4: Expand Around Center
Expansion around the center considers each character (and each pair of adjacent characters) as the potential center of a palindrome. It then systematically expands around the center checking for palindromic sequences. Each expansion takes constant time and is efficient for finding the longest palindromic substring, which is useful as part of a greater method for subsequences.
Here’s an example:
def expand_around_center(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r-l-1
max_length = 0
for i in range(len(s)):
len1 = expand(i, i)
len2 = expand(i, i+1)
max_length = max(max_length, max(len1, len2))
return max_length
string = "character"
print(expand_around_center(string))
Output: 3
This method uses a helper function to expand from the center and finds the length of potential palindromic substrings. However, this approach only finds the longest palindrome substring, not subsequence. With minor adaptations, it can be combined with other methods for subsequences to improve efficiency.
Bonus One-Liner Method 5: Recursive Solution
A simple recursive solution can find the longest palindromic subsequence by checking whether the first and last characters match and then making recursive calls to the rest of the string, although this is highly inefficient without memoization.
Here’s an example:
def lps(s):
if len(s) <= 1:
return len(s)
if s[0] == s[-1]:
return 2 + lps(s[1:-1])
return max(lps(s[1:]), lps(s[:-1]))
print(lps("character"))
Output: 5
This one-liner approach succinctly demonstrates the concept of recursion for finding palindromic subsequences. The base cases account for strings of length one or less, and the recursive steps maximize the length by including or not including end characters. It is elegant but has exponential time complexity.
Summary/Discussion
- Method 1: Dynamic Programming. Highly efficient and the standard solution for this problem. It has a polynomial time complexity but requires O(n^2) space, which can be a drawback for very long strings.
- Method 2: Recursion with Memoization. Improves the basic recursive solution’s time complexity significantly, making it more practical for use, but still has high space complexity due to the memoization cache.
- Method 3: Using the Longest Common Subsequence. This method also has good efficiency and is based on a well-understood problem, but creating a reversed copy of the string doubles the space requirement.
- Method 4: Expand Around Center. Fast for finding the longest palindromic substring but requires additional handling for subsequences. It’s an efficient method when modified appropriately.
- Bonus One-Liner Method 5: Recursive Solution. It is simple and elegant but has poor performance for larger strings due to its exponential time complexity, making it mostly of theoretical interest.