Grokking Dynamic Programming Interview/

...

/

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 ≤5000\leq 5000

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
Java
usercode > Main.java
public class Main{

    public static int longestPalindromicSubsequence(String 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:

import java.util.*;
class Palindrome {
    public static int longestPalindromicSubsequence(String s) {
        int length = s.length();
        return longestPalindromicSubsequenceRecursive(s, 0, length - 1);
    }
    public static int longestPalindromicSubsequenceRecursive(String s, int startIndex, int endIndex) {
        if (startIndex > endIndex) return 0;
        // Every sequence with one element is a palindrome of length 1
        if (startIndex == endIndex) return 1;
        // Case 1: elements at the beginning and the end are the same
        if (s.charAt(startIndex) == s.charAt(endIndex))
            return 2 + longestPalindromicSubsequenceRecursive(s, startIndex + 1, endIndex - 1);
        // Case 2: skip one element either from the beginning or the end
        int c1 = longestPalindromicSubsequenceRecursive(s, startIndex + 1, endIndex);
        int c2 = longestPalindromicSubsequenceRecursive(s, startIndex, endIndex - 1);
        return Math.max(c1, c2);
    }
    public static void main(String[] args) {
        ArrayList < String > strings = new ArrayList < String > (
            Arrays.asList("cddpd", "abdbca", "racecar", "pqr")
        );
        // You can uncomment the lines below and check how this recursive solution causes a time-out
        // strings.add("aeqirradarqwruifdfgdtrrrraaadddaqweraarrr");
        int index = 0;
        for (String input: strings) {
            System.out.println((++index) + ". The length of the longest plaindromic subsequence in '" + input + "' is: " + longestPalindromicSubsequence(input));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
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.