题目

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

Example 1:

Input: s = “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: s = “cbbd”
Output: “bb”
Example 3:

Input: s = “a”
Output: “a”
Example 4:

Input: s = “ac”
Output: “a”

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

解法：枚举

由于字符串长度小于1000，因此我们可以用 O(n2)O(n2) 的算法枚举所有可能的情况。
首先枚举回文串的中心 ii，然后分两种情况向两边扩展边界，直到遇到不同字符为止:

• 回文串长度是奇数，则依次判断 s[i−k]==s[i+k],k=1,2,3,…s[i−k]==s[i+k],k=1,2,3,…
• 回文串长度是偶数，则依次判断 s[i−k]==s[i+k−1],k=1,2,3,…s[i−k]==s[i+k−1],k=1,2,3,…

如果遇到不同字符，则我们就找到了以 ii 为中心的回文串边界。

时间复杂度O(n2)，空间复杂度O(1)

class Solution {
public:
    string longestPalindrome(string s) {
        string ans;
        for (int i = 0; i < s.size(); i++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
            if (ans.size() < r - l - 1) ans = s.substr(l + 1, r - l - 1);
            l = i, r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
            if (ans.size() < r - l - 1) ans = s.substr(l + 1, r - l - 1);
        }
        return ans;
    }
};