老规矩，先上代码，后面有解题思路。

//// Created by tannzh on 2020/6/12.///* * 最长回文子串给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2：输入: "cbbd"输出: "bb"通过次数291,057提交次数947,907 */#include <iostream>#include <string>using namespace std;class Solution {public:    string longestPalindrome(string s) {        int len = s.size();        if (len == 0) return s;        int start = 0, last = 0;        for (int i=0; i<len-1; ++i) {            longestPalindrome(s, i, i, start, last);            longestPalindrome(s, i, i+1, start, last);        }        return s.substr(start, last-start+1);    }private:    void longestPalindrome(const string& s, int b, int e, int &start, int &last) {        int len = s.size();        while (b >= 0 && e < len && s[b] == s[e])            --b, ++e;        ++b, --e;        if (e - b > last - start) {            start = b;            last = e;        }    }};int main(int argc, char **argv){    Solution s;    std::string test1 = "babad";    std::string test2 = "cbbd";    std::cout << "test1 result: " << s.longestPalindrome(test1) << std::endl;    std::cout << "test2 result: " << s.longestPalindrome(test2) << std::endl;    return 0;}

假设 S(i, j) 为问题的解，即从位置 `i` 到 `j` 的字符串是 Longest Palindromic Substring of the string.

我们从最简单的字符串来想：

a

单字符本身是否是回文？是。即 S(i, i)

a a

两个相同字符是否组成回文？是。即 S(i, i+1) when `s[i] == s[i+1]`.

b a a b

为上面的回文字符串首尾增加一个相同的字符 `b`, 组成了回文，即 S(i, j) when S(i+1, j-1) and `s[i] == s[j]`.

由于我们持续在首尾增加字符，对于单字符，则长度一直为奇数；对于双字符，则长度一直为偶数。所以要涵盖所有情况，需要分别验证这两种情况。

好了，分析到这里基本可以明白回文的规律所在了。

要求的是长度，那么我们记 Longest Palindromic Substring 为 longest.