Today I am going to show how to solve the Longest Palindromic Substring.

Here is the problem:

In my last blog I talked about how to determine whether or not a string is a palindrome. A palindrome is a string that's written the same forward as backward.

But this problem is a bit different in that not only do we have to find out if a string is a palindrome, we also have to find the longest palindromic substring.

Before diving into the solution, I’d like to note that a single character is considered a palindrome. For instance, the letter 'a' alone is considered to be a palindrome because it's written the same forward as backward.

We know that every palindrome has a center. If it's of odd length, then the center of the palindrome is a letter. But if it's of even length, then the center of the palindrome is just in between two letters.

We can iterate through our input string and treat each given point as if it could be the center of a palindrome. The center could be at the given letter, or between the given letter and the previous letter. When we are in the middle of a palindrome, we can then expand and look at the two next letters to the side of it and see if they're equal to each other. And then update our current longest palindrome accordingly.

We never actually have to store the palindromes; we can just store the index of the starting letter of the palindrome and the index of the last letter.

We essentially continue to check the center of a potential palindrome and expand from it. And that's going to end up running in O(n^2).

var longestPalindrome = function(s) {
    let currentLongest = [0, 1];

    for (let i=1; i< s.length; i++){
        const odd = expandAroundCenter(s, i-1, i+1); // treating the given letter as a center and checking its surrounding letters 
        const even = expandAroundCenter(s, i-1, i); // checking if the  center is between the given letter and the previous letter
        const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even; // choosing the longest palindrome between odd and even
        currentLongest = currentLongest[1] - currentLongest[0] > longest [1] - longest[0] ?  currentLongest : longest // comparing the longest to the current longest palindrome and updating current longest accordingly
    } 
    return s.slice(currentLongest[0], currentLongest[1]);
};

function expandAroundCenter(s, leftIdx, rightIdx){
    while (leftIdx >= 0 && rightIdx < s.length){
        if(s[leftIdx] !== s[rightIdx]) break;
        leftIdx--;
        rightIdx++;
    }
    return[leftIdx + 1, rightIdx] 
}