5. Longest Palindromic Substring

Longest Palindromic Substring

Problem Description 

Given a string s, return the longest palindromic substring in s.

A string is called a palindrome string if the reverse of that string is the same as the original string.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Explanation:
In this LeetCode challenge we’re asked to find the longest palindrome in a given string (a palindrome being a sequence of characters that is the same backwards as it is forwards, such as “bob”).

Now you might be inclined to think that the solution to this is simply to look at every character, and then move outwards until the characters no longer mirror each other. However, whilst this would work for a string like “aba”, it would not work for a string like “abba”, so we need to look for mirrored characters both by individual letter, and by letter-couple

Approach) Loop, call twice, and store globally
Not a catchy title I know, but as this is my only real solution a catchy name seemed unnecessary!
In this solution, we loop through all characters in the string, and for each one, we begin checking for palindromes both on the current character and on the current character-couple. For each palindrome found, we check if it’s the new longest one, and store it if so.

Let`s Code IT!
var longestPalindrome = function (string) {
    let longestPal = '';

    var getLongestPalindrome = function (leftPosition, rightPosition) {
        // While there is space to expand, and the expanded strings match
        while (
            leftPosition >= 0 &&
            rightPosition < string.length &&
            string[leftPosition] === string[rightPosition]
        ) {
            // Expand in each direction.
            leftPosition--;
            rightPosition++;
        }

        // Store the longest palindrom (if it's the longest one found so far)
        if (rightPosition - leftPosition > longestPal.length) {
            longestPal = string.slice(leftPosition + 1, rightPosition);
        }
    };

    // Loop through the letters
    for (let i = 0; i < string.length; i++) {
        // Find the longest odd palendrome
        getLongestPalindrome(i, i + 1);

        // Find the longest even palendrome
        getLongestPalindrome(i, i);

        // Check if a longer palindrome cannot be found
        if ((string.length - i) * 2 < longestPal.length) {
            // Break out to avoid unnecessary computation
            break;
        }
    }

    return longestPal;
};

This solution works great, and is pretty quick. In fact, the only way I’ve found to improve its performance is to replace the somewhat expensive string storing operations with pointer storage instead. In other words, instead of storing (and subsequently overwriting) the longest palindromes found each time, we instead store (and overwrite) pointers to the start and end of the longest palindrome. As you can imagine, once we get seriously long strings, this really starts to improve performance (at the cost of readability).

var longestPalindrome = function (string) {
    let longestPalLength = 0;
    let longestPalLeft = 0;
    let longestPalRight = 0;

    var getLongestPalindrome = function (leftPosition, rightPosition) {
        // While there is space to expand, and the expanded strings match
        while (
            leftPosition >= 0 &&
            rightPosition < string.length &&
            string[leftPosition] === string[rightPosition]
        ) {
            //expand in each direction.
            leftPosition--;
            rightPosition++;
        }

        // Store the longest palindrome (if it's the longest one found so far)
        if (rightPosition - leftPosition > longestPalLength) {
            longestPalLeft = leftPosition + 1;
            longestPalRight = rightPosition - 1;
            longestPalLength = longestPalRight - longestPalLeft + 1;
        }
    };

    // Loop through the letters
    for (let i = 0; i < string.length; i++) {
        // Find the longest odd palendrome
        getLongestPalindrome(i, i + 1);

        // Find the longest even palendrome
        getLongestPalindrome(i, i);

        // Check if a longer palindrome cannot be found
        if ((string.length - i) * 2 < longestPalLength) {
            // Break out to avoid unnecessary computation
            break;
        }
    }

    return string.slice(longestPalLeft, longestPalRight + 1);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #5. Longest Palindromic Substring
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!