5. Longest Palindromic Substring

Problem

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  var start = 0;
  var end = 0;
  var len = s.length;
  var num = 0;
  for (var i = 0; i < len; i++) {
    num = Math.max(expandAroundCenter(s, i, i), expandAroundCenter(s, i, i + 1));
    if (num > end - start) {
      start = i - Math.floor((num - 1) / 2);
      end = i + Math.floor(num / 2);
    }
  }
  return s.slice(start, end + 1);
};

var expandAroundCenter = function (s, left, right) {
  var l = left;
  var r = right;
  var len = s.length;
  while (l >= 0 && r < len && s[l] === s[r]) {
    l--;
    r++;
  }
  return r - l - 1;
};

Explain:

遍历每个字符，检查以这个字符或相邻两个字符为中心是否回文，记录最长的回文字符位置。

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(1).

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let startIndex = 0;
    let maxLength = 1;

    function expandAroundCenter(left, right) {
        while (left >=0 && right < s.length && s[left] === s[right]) {
            const currentPalLength = right - left + 1;
            if (currentPalLength > maxLength) {
                maxLength = currentPalLength;
                startIndex = left;
            }
            left -= 1;
            right += 1;
        }
    }

    for (let i = 0; i < s.length; i++) {
            expandAroundCenter(i-1, i+1);
            expandAroundCenter(i, i+1);
        }

    return s.slice(startIndex, startIndex + maxLength)
};

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(1).