Longest Palindromic Substring（最长回文子串）

题目 / Problem

中文： 给定一个字符串 s，返回 s 中最长的回文子串。

回文字符串从左向右和从右向左读取的内容相同。子串必须是原字符串中连续的一段字符。

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

A palindrome reads the same from left to right and right to left. A substring must consist of consecutive characters from the original string.

示例 / Examples

Example 1

Input:  s = "babad"
Output: "bab"

"aba" 也是长度为 3 的最长回文子串，因此同样是合法答案。
"aba" is another longest palindromic substring of length 3, so it is also valid.

Example 2

Input:  s = "cbbd"
Output: "bb"

最长回文子串的中心位于两个 'b' 之间。
The center of the longest palindrome lies between the two 'b' characters.

约束 / Constraints

1 <= s.length <= 1000
s 只包含数字和英文字母。
s consists only of digits and English letters.

解题思路：中心扩展 / Approach: Expand Around Center

任何回文串都可以从中心向两侧扩展。只要左右字符相同，就可以继续扩大回文范围。
Every palindrome can be expanded outward from its center. As long as the left and right characters match, the palindromic range can continue growing.

回文串有两种中心形式：
There are two types of palindrome centers:

奇数长度 / Odd Length

中心是某一个字符：
The center is a single character:

"racecar"
    ↑
  center

初始左右指针相同：
Initialize both pointers to the same index:

left = center;
right = center;

偶数长度 / Even Length

中心位于两个字符之间：
The center lies between two characters:

"abba"
   ↑
 center

初始左右指针相邻：
Initialize the pointers to adjacent indices:

left = center;
right = center + 1;

对于字符串中的每个位置，都分别尝试这两种中心，即可覆盖所有可能的回文子串。
For every position in the string, try both center types to cover every possible palindromic substring.

扩展过程 / Expansion Process

当以下条件同时满足时继续扩展：
Continue expanding while all these conditions hold:

left >= 0
right < s.length
s[left] === s[right]

while (
  left >= 0 &&
  right < s.length &&
  s[left] === s[right]
) {
  left--;
  right++;
}

循环结束时，left 和 right 已经分别越过回文子串的真实边界，因此实际范围是：
When the loop ends, left and right have moved one step beyond the palindrome's true boundaries, so the actual range is:

[left + 1, right - 1]

对应长度为：
Its length is:

right - left - 1

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
  let bestStart = 0;
  let bestLength = 1;

  function expand(left, right) {
    while (
      left >= 0 &&
      right < s.length &&
      s[left] === s[right]
    ) {
      left--;
      right++;
    }

    const currentStart = left + 1;
    const currentLength = right - left - 1;

    if (currentLength > bestLength) {
      bestStart = currentStart;
      bestLength = currentLength;
    }
  }

  for (let center = 0; center < s.length; center++) {
    // 奇数长度回文 / Odd-length palindrome
    expand(center, center);

    // 偶数长度回文 / Even-length palindrome
    expand(center, center + 1);
  }

  return s.slice(bestStart, bestStart + bestLength);
}

执行过程 / Walkthrough

以 s = "babad" 为例：
For s = "babad":

中心 / Center	类型 / Type	扩展得到 / Palindrome	长度 / Length
`0` (`b`)	奇数 / Odd	`"b"`	1
`1` (`a`)	奇数 / Odd	`"bab"`	3
`2` (`b`)	奇数 / Odd	`"aba"`	3
`3` (`a`)	奇数 / Odd	`"a"`	1
`4` (`d`)	奇数 / Odd	`"d"`	1

第一次找到长度为 3 的 "bab" 后，"aba" 的长度与当前最佳结果相同。代码只在找到更长结果时更新，因此最终返回 "bab"。题目也允许返回 "aba"。
After first finding "bab" of length 3, "aba" ties the current best. The code updates only for a strictly longer result, so it returns "bab"; the problem also accepts "aba".

偶数长度示例 / Even-Length Example

对于 s = "cbbd"，在下标 1 和 2 之间进行偶数中心扩展：
For s = "cbbd", expand around the even center between indices 1 and 2:

c b b d
  ↑ ↑
left right

两个字符都为 'b'，所以得到回文子串 "bb"。继续向外时 'c' !== 'd'，扩展停止。
Both characters are 'b', producing "bb". Expansion then stops because 'c' !== 'd'.

为什么不用暴力枚举？ / Why Not Brute Force?

暴力方法会枚举 O(n²) 个子串，并用 O(n) 时间检查每个子串是否为回文，因此总时间复杂度为 O(n³)。
A brute-force solution enumerates O(n²) substrings and spends O(n) checking each one, for a total of O(n³) time.

中心扩展直接利用回文的对称结构，把总时间降低到 O(n²)。
Center expansion uses palindrome symmetry directly, reducing the total time to O(n²).

另一种方法：动态规划 / Alternative: Dynamic Programming

也可以定义：
Another approach defines:

dp[left][right] = s[left...right] 是否为回文
dp[left][right] = whether s[left...right] is a palindrome

状态转移为：
The transition is:

s[left] === s[right]
并且 / and
right - left <= 2 或 dp[left + 1][right - 1] 为 true
right - left <= 2 or dp[left + 1][right - 1] is true

动态规划同样需要 O(n²) 时间，但还需要 O(n²) 空间。中心扩展法只使用常数额外空间，因此更适合作为本题的主要解法。
Dynamic programming also takes O(n²) time but requires O(n²) space. Center expansion uses only constant extra space, making it the preferred solution here.

复杂度 / Complexity

字符串有 2n - 1 个可能的中心，每次扩展最坏需要 O(n) 时间。
A string has 2n - 1 possible centers, and each expansion may take O(n) time in the worst case.

时间复杂度 / Time: O(n²)
辅助空间 / Auxiliary space: O(1)，不计算返回的子字符串。
O(1), excluding the returned substring.

易错点 / Common Pitfalls

必须同时检查奇数长度和偶数长度的回文中心。
Check both odd-length and even-length palindrome centers.
扩展结束后，真实起点是 left + 1，不是 left。
After expansion, the true starting index is left + 1, not left.
扩展结束后的回文长度是 right - left - 1。
The palindrome length after expansion is right - left - 1.
子串必须连续；不能跳过字符组成回文。
A substring must be contiguous; characters cannot be skipped.
当存在多个相同最大长度的答案时，返回其中任意一个即可。
If multiple longest palindromes exist, any one of them may be returned.
保存起点和长度即可，不必在每次扩展时创建新的子字符串。
Track the starting index and length instead of creating a new substring after every expansion.

Longest Palindromic Substring