5. Longest Palindromic Substring

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

JS解法

从头至尾遍历字符串，找其最长子串O(n^2)。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  if (s.length < 2) return s;
  let minStart = 0, maxLen = 1;
  let curIndex = 0;
  while (curIndex < s.length) {
    if (s.length - curIndex < maxLen / 2) break;
    let j = k = curIndex;
    while (k < s.length - 1 && s[k+1] === s[k]) ++k; // Skip duplicate characters.
    curIndex = k + 1;
    while (k < s.length - 1 && j > 0 && s[k+1] === s[j-1]) {
      ++k;
      --j;
    }
    let newLen = k - j + 1;
    if (newLen > maxLen) {
      minStart = j;
      maxLen = newLen;
    }
  }
  return s.substr(minStart, maxLen);
};