Longest palindromic substring in s

This problem was asked by Uber.

You are given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example

function longestPalindrome(s) {

}

console.log(longestPalindrome('babad')); // bab
console.log(longestPalindrome('cbbd')); // bb

Solution

function longestPalindrome(s) {
  let longest = "";
  for (let i = 0; i < s.length; i++) {
    const oddStr = expandFromMiddle(s, i, i);
    if (oddStr.length > longest.length) {
      longest = oddStr;
    }

    const evenStr = expandFromMiddle(s, i, i + 1);
    if (evenStr.length > longest.length) {
      longest = evenStr;
    }
  }

  function expandFromMiddle(str, left, right) {
    while (left >= 0 && right < str.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return str.slice(left + 1, right);
  }
  return longest;
}

Explanation

• Iterate through each character in the string
• For each character, expand outwards to find odd and even length palindromes centered at that character
• Use a helper function to expand from the middle, incrementing left and right pointers until reaching different characters
• Keep track of the longest palindrome seen so far
• After checking all characters, return the longest palindrome