516. Longest Palindromic Subsequence
Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
One possible longest palindromic subsequence is “bbbb”.
One possible longest palindromic subsequence is “bb”.
1 <= s.length <= 1000
sconsists only of lowercase English letters.
Before we move to the solution, let us understand the meaning of subsequence and palindrome.
According to Wikipedia,
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Now let us compare the given problem statement and the Longest Common Subsequence.
We see that both the question seems slightly similar. The difference is one requires a common subsequence and has two input strings, while the other requires palindromic subsequence and has one input string. This tells us that we might need to perform some additional steps to use the LCS algorithm.
Since one of the differences between both is the difference in the number of the input string. To solve this problem, we can use the same input string twice. Since we need to find palindromic subsequence, we will be reversing the second string. Why do we need to reverse the string though? A palindrome is a word that reads the same forward and backward. This means the first character should be equal to the last character. If we reverse the string, we can check if the first character is equal to the last characters using the matrix method used in the LCS algorithm.
Since we have learned the LCS algorithm before, we won't be repeating the steps.
Let us look into the code snippet.
def longestPalindromeSubseq(self, s: str) -> int:
memo = [[0 for j in range(len(s)+1)]for i in range(len(s)+1)]
rev_s = s[::-1]
for i in range(1, len(memo)):
for j in range(1, len(memo)):
if s[i-1] == rev_s[j-1]:
memo[i][j] = memo[i-1][j-1]+1
memo[i][j] = max(memo[i][j-1], memo[i-1][j])
We are traversing through a 2D array of size N², hence the time complexity is O(N²), where N is the size of the string.
We are creating a 2D array of size N², hence the space complexity is O(N²), where N is the size of the string
Link to Aditya Verma’s video