Grokking Dynamic Programming Interview in Python/

...

/

Longest Palindromic Subsequence

Longest Palindromic Subsequence

Let's solve the Longest Palindromic Subsequence problem using Dynamic Programming.

We'll cover the following...

Statement

Given a string, find the length of the longest palindromic subsequence if it exists. In a palindromic subsequence, elements read the same backward and forward.

A subsequence is a sequence that can be derived from another sequence by deleting or keeping some elements without changing the order of the remaining elements.

Let’s say that we are given a string “abbca” to find its longest palindromic subsequence. We see in this example that if we ignore “c” in the given string, we get the longest palindrome (“abba”) of this sequence which has a length of 44.

Constraints:

  • s consists of lowercase letters.

  • 1≤1 \leq s.length ≤900\leq 900

Examples

No.

s

Length

1

racecar

7

2

abbca

4

3

cddpd

3

Try it yourself

Implement your solution in the following playground.

Press + to interact
Python
usercode > main.py
def longest_palindromic_subsequence(s):

    

    # write your code here



    return -1
Longest Palindromic Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using dynamic programming.

Naive approach

The naive solution for this problem is to generate all subsequences of the given sequence and find the longest palindromic subsequence.

The longest palindromic subsequence can be solved using recursion. Therefore, to find the longest palindromic subsequence of s, we start from the first and the end index of s, and at each recursive step, we follow the following steps:

  • If the start and end indices are the same, we are at a single character, a palindrome with length 1. Therefore, we return 1.

  • If the elements at the start and end index are the same while the indexes are different, we increase the count by 2 and make a recursive call to the rest of the string.

  • If the elements are not the same, skip the element from the start or the end, make a recursive call to both choices and choose the maximum count from both of the calls.

Let’s try to implement the algorithm discussed above:

def longest_palindromic_subsequence(s):
    return longest_palindromic_subsequence_recursive(s, 0, len(s) - 1)
def longest_palindromic_subsequence_recursive(s, start_index, end_index):
    if start_index > end_index:
        return 0
    # Every sequence with one element is a palindrome of length 1
    if start_index == end_index:
        return 1
    # Case 1: elements at the beginning and the end are the same
    if s[start_index] == s[end_index]:
        return 2 + longest_palindromic_subsequence_recursive(s, start_index + 1, end_index - 1)
    # Case 2: skip one element either from the beginning or the end
    c1 = longest_palindromic_subsequence_recursive(s, start_index + 1, end_index)
    c2 = longest_palindromic_subsequence_recursive(s, start_index, end_index - 1)
    return max(c1, c2)
# Driver code to test the above function
if __name__ == '__main__':
    strings=['cddpd', 'abdbca','racecar','pqr']
    # You can uncomment the lines below and check how this recursive solution causes a time-out
    
    # strings.append('aeqirradarqwruirrraaadddaqweraarrr')
    
    for i in range(len(strings)):
        print(str(i+1)+". The length of the longest palindromic subsequence in '", strings[i] ,"' is: ",longest_palindromic_subsequence(strings[i]), sep="")
        print("-"*100)
Longest Palindromic Subsequence using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity

The time complexity of the algorithm above is exponential O(2n) ...

Access this course and 1400+ top-rated courses and projects.