最长回文子串

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.

Idea

Every palindrome mirrors around its center, which is either one character (odd length) or the gap between two characters (even length). For each of the \(2n - 1\) possible centers, expand around the center with two pointers moving outward while the characters match, and keep the longest palindrome found.

A dynamic programming table, where dp[i][j] tells whether s[i..j] is a palindrome, also works in \(O(n^2)\) time, but it needs \(O(n^2)\) space.

Time complexity: \(O(n^2)\), Space complexity: \(O(1)\), where \(n\) is the length of s

Pseudo Code

start = 0;
maxLen = 1;
for (i = 0; i < n; i++) {
    len1 = expand(s, i, i);        // odd length, center at i
    len2 = expand(s, i, i + 1);    // even length, center between i and i + 1
    len = max(len1, len2);
    if (len > maxLen) {
        maxLen = len;
        start = i - (len - 1) / 2;
    }
}
return s.substring(start, start + maxLen);

int expand(s, left, right) {
    while (left >= 0 && right < n && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}