Grokking Dynamic Programming Interview/

...

/

Longest Palindromic Substring

Longest Palindromic Substring

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

We'll cover the following...

Statement

Given a string s, find the length of its longest palindromic substring. The longest palindromic substring is a substring with maximum length that is also a palindrome. A phrase, word, or sequence is a palindrome that reads the same forward and backward.

For example, consider the string "bobgonoon". The palindromic substrings of "bobgonoon" are listed below:

Substring length

Substrings

1

"b", "o", "g", "n"

2

"oo"

3

"bob", "ono"

4

"noon"

The longest of them is "noon". Therefore, the length of the longest palindromic substring of "bobgonoon" is 4.

Constraints:

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

  • s consists of only lowercase letters.

Examples

No.

String

Longest Palindromic Substring Length

1

abcbq

3

3

dadxracecarpmadam

7

Try it yourself

Implement your solution in the following playground.

Press + to interact
Java
usercode > Main.java
import java.util.*;



class Main {

    public static int findLpsLength(String s){



        // Write your code here

        

        return -1;

    }

}
Longest Palindromic Substring

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 the Palindromic Subsequence dynamic programming pattern.

Naive approach

A naive approach to this problem is to find all possible substrings, check whether each string is palindrome or not, and then select the string with the maximum length. A recursive solution that implements this approach is explained below:

  • Start two pointers from the start and end of the string.

  • If the characters at the two indexes match, recursively check if the substring between these two indexes is also a palindrome. If it's a palindrome, then it's the longest palindromic substring.

  • If the characters at the two indexes don't match, divide the problem into two subproblems by dropping a character from the start and end of the string. Call recursion on each subproblem to check if the strings are palindromes, and take the maximum length of the two substrings.

import java.util.stream.*;
import java.util.*;
class LongestPalindromicSubstring {
    public static int findLpsLengthRecursion(String s, int start, int end){
        // if both pointers are pointing to the same index
        if (start==end)
            return 1;
        // the characters at start and end indices match
        if (s.charAt(start)==s.charAt(end)){
            int subStringLength = end - start + 1;
            // if the substring length is 2 and it's also a palindrome
            if (subStringLength == 2)
                return 2;
            // check whether the remainig string is a palindrome
            if (subStringLength == 2 + findLpsLengthRecursion(s, start+1, end-1))
                return subStringLength;
        }
        // skip one element either from the beginning or end and select the maximum resultant value
        return Math.max(findLpsLengthRecursion(s, start+1, end), findLpsLengthRecursion(s, start, end-1));
    }
    public static int findLpsLength(String s){
        return findLpsLengthRecursion(s, 0, s.length()-1);
    }
    // Driver code
    public static void main(String[] args) {
        ArrayList<String> strings = new ArrayList<String>(
            Arrays.asList("abcbda", "tworacecars", "pqrssrqp", "mnop", "bbbbbbbbbbbbbbbbbbbb"));
        
        // You can uncomment the line below and check how this recursive solution causes a time-out
        // strings.add("mwusjunybvgafxuhloqwfoizqkkqzilltjw");
        for (int i=0; i<strings.size(); ++i){
            System.out.println(i+1+".\t Input string: '" + strings.get(i) + "'");
            System.out.println("\t Length of the longest palindromic substring: " + findLpsLength(strings.get(i)));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Longest Palindromic Substring 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 below and see the difference.

Time complexity

The time complexity of the algorithm above is exponential O(n3)O(n^3), where ...