Longest Palindromic Substring

Problem

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

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.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let palindrome = "";
    for (let i = 0; i < s.length; i++) {
        const string1 = expandAroundCentre(s, i - 1, i + 1, s[i]);  // odd length
        const string2 = expandAroundCentre(s, i, i + 1, "");  // even length
        if (palindrome.length < string1.length) {
            palindrome = string1;
        }
        if (palindrome.length < string2.length) {
            palindrome = string2;
        }
    }
    return palindrome;
};

var expandAroundCentre = function(s, left, right, centre) {
    let string = centre;
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        string = s[left] + string + s[right];
        left -= 1;
        right += 1;
    }
    return string;
};

We find the longest palindrome by trying every possible palindrome centre and expanding around it (ie. given a palindrome, if the characters directly before and after it are the same, we must have a longer palindrome). There are 2n - 1 of such centres that needs to be tested, while keeping track of the longest palindrome.

Problem​

Solution​

Problem

Solution