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)
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.