给定一个字符串，求字符串中最长的回文子串。
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

思路：
一、暴力解决，O(n^3) 的时间复杂度，最外层循环为 子串的起始位置，第二层循环为，对字符串中的字符遍历，若与子串的第一个字符相等，则停下来验证这一个子串是否是回文，第里层循环为回文验证。由于“bb……bb”这种字符串，第一次遍历后就得到了结果，不需要再进寻找，所以，需要对程序剪枝，尽量减小时间复杂度。虽然能AC，但时间复杂度还是太高了。

string longestPalindrome(string s) {
    string res = "" , tmp = "";
    for (int l = 0; l < (int)s.size(); l++) { //子串起始位置
        for (int i = l; i < (int)s.size(); i++) { //字符串遍历
            if (s[i] == s[l]) {
                tmp = s.substr(l, i - l + 1);
                int tmp_size = tmp.size(), flag = 1;
                for (int j = 0; j < tmp_size/2; j++) { //回文判断
                    if (tmp[j] != tmp[tmp_size - 1 - j]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) res = tmp.size() > res.size() ? tmp : res;//更新结果
            }
        }
        if ((int)res.size() >= (int)(s.size() - l)) break;//剪枝
    }
    return res;
 }

 

二、从中间往两边扩，时间复杂度O( n^2 )，但是要注意回文个数为奇数个、偶数个，偶数个的话必然中间至少有两个是相等的，比如 noon 中间的 oo相等，而奇数个的话，比如 aba ，可以不管 'b'，下标l和r = b的下标，直接对比左边 l-1和右边 r+1的字符是否相等。所以，在处理偶数个时，将 oo 视为一个 O ，即：这儿需要保持 l 不变，将 r 向右移，noon可以看成  nOn，，然后当做奇数处理。

string longestPalindrome(string s) {
    if (s.size() < 2) return s;
    string res = "";
    int n = s.size();
    for (int i = 0; i < n;) {
        int l = i, r = i;
        while (r < n - 1 && s[r] == s[r + 1]) r++;//处理偶数个，r右移
        i = r + 1;
        while (r < n - 1 && l>0 && s[r + 1] == s[l - 1]) {//处理奇数个
            l--;
            r++;
        }
        if ((int)res.size() < r - l + 1) res = s.substr(l, r - l + 1);
    }
    return res;
 }