Grokking Dynamic Programming Interview in JavaScript/

...

/

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
JavaScript
usercode > main.js
function findLpsLength(s) {

    

    // Write your code here



    return -1;

}



export { findLpsLength };
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.

function findLpsLengthRecursion(s, start, 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[start]==s[end]){
        let 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));
}
function findLpsLength(s) {
    return findLpsLengthRecursion(s, 0, s.length-1);
}
export { findLpsLength };
// Driver code
function main() {
    let strings = ["abcbda", "tworacecars", "pqrssrqp", "mnop", "bbbbbbbbbbbbbbbbbbbb"];
    // You can uncomment the line below and check how this recursive solution causes a time-out
    // strings.push("mwusjunybvgafxuhloqwfoizqkkqzilltjw");
    strings.map((s, i) => {
        console.log(i + 1 + ".\t Input string: " + s);
        console.log("\t Length of the longest palindromic substring: " + findLpsLength(s));
        console.log("-".repeat(100));
    });
}
main();
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 ...