Longest Palindromic Subsequence — Day 63(Python)

Photo by Daniele Levis Pelusi on Unsplash

Today’s question is a variation of the Longest Common Subsequence. Let us look into the question without wasting much time.

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.

Example 1:
Input:

Output:

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

Output:

One possible longest palindromic subsequence is “bb”.

Constraints:

  • 1 <= s.length <= 1000
  • s consists 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.

A palindrome is a word, number, phrase, or other sequences of characters which reads the same backward as forward, such as madam or racecar.

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.

Complexity analysis.

Time Complexity

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.

Space Complexity.

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

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt