Longest Palindromic Subsequence in Python
Longest Palindromic Subsequence (LPS) problem is about finding the longest subsequence of the given sequence which is a palindrome. In Python, the task of maximizing the number of words in a sentence can be solved by the methods of dynamic programming.
The algorithm for finding the Longest Palindromic Subsequence involves creating a table to store the lengths of the longest palindromic subsequences for different substrings of the input sequence.
Longest Palindromic Subsequence in Python using Memoization:
Step-by-step algorithm:
- Define a recursive function, say lps(s1, s2, n1, n2) which finds the longest common subsequence among s1 and s2 where n1 is index of s1 and n2 is index of s2.
- Call the lps function with input string seq as s1 and reverse of seq as s2.
- If we reach the first index of any string, return 0
- Check if we have already computed the result for the current indices.
- If the result is already computed, return the result.
- Otherwise, if the current indices of both s1 and s2 are equal, dp[n1][n2] = 1 + lps(s1, s2, n1 – 1, n2 – 1)
- Else if the current index of both s1 and s2 are not equal, dp[n1][n2] = max(lps(s1, s2, n1 – 1, n2), lps(s1, s2, n1, n2 – 1))
- Store the above result in dp[n1][n2]
Below is the implementation of Longest Palindromic Subsequence in Python using Memoization:
# A Dynamic Programming based Python program for LPS problem
# Returns the length of the longest palindromic subsequence
# in seq
dp = [[-1 for i in range(1001)]for j in range(1001)]
# Returns the length of the longest palindromic subsequence
# in seq
def lps(s1, s2, n1, n2):
if (n1 == 0 or n2 == 0):
return 0
if (dp[n1][n2] != -1):
return dp[n1][n2]
if (s1[n1 - 1] == s2[n2 - 1]):
dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1)
return dp[n1][n2]
else:
dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1))
return dp[n1][n2]
# Driver program to test above functions
seq = "w3wiki"
n = len(seq)
s2 = seq
s2 = s2[::-1]
print(f"The length of the LPS is {lps(s2, seq, n, n)}")
Output
The length of the LPS is 5
Time Complexity: O(n2), where n is the length of the input string
Auxiliary Space: O(n2)
Longest Palindromic Subsequence in Python using Tabulation:
Step-by-step algorithm:
- Initialize a 2D array dp with dimensions (n x n), where n is the length of the input sequence.
- Set the diagonal elements of dp to 1, as each single character is a palindrome of length 1.
- Traverse the input sequence with two pointers i and j, where i starts from n-1 and decrements, and j starts from i+1 and increments.
- If seq[i] is equal to seq[j], set dp[i][j] to dp[i+1][j-1] + 2 because the current characters form a palindromic subsequence of length 2 greater than the one inside them.
- Otherwise, set dp[i][j] to the maximum of dp[i+1][j] and dp[i][j-1], as we discard one character from either end and try to find the longest palindromic subsequence.
- The result is stored in dp[0][n-1], which represents the length of the Longest Palindromic Subsequence.
Below is the implementation of Longest Palindromic Subsequence in Python using Tabulation:
def longestPalinSubseq(S):
R = S[::-1]
# dp[i][j] will store the length of the longest
# palindromic subsequence for the substring
# starting at index i and ending at index j
dp = [[0] * (len(R) + 1) for _ in range(len(S) + 1)]
# Filling up DP table based on conditions discussed
# in the above approach
for i in range(1, len(S) + 1):
for j in range(1, len(R) + 1):
if S[i - 1] == R[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
# At the end, DP table will contain the LPS
# So just return the length of LPS
return dp[len(S)][len(R)]
# Driver code
s = "w3wiki"
print("The length of the LPS is", longestPalinSubseq(s))
Output
The length of the LPS is 5
Time Complexity: O(n2), where n is the length of the input string
Auxiliary Space: O(n2)