题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

算法思想

1. 确认回文中心i 和两边短点l 和 r 从而确认最大长度maxv
2. 回文中心分奇数和偶数，利用for循环遍历整个字符串得到最大的回文子串

class Solution {

  //返回字符串s回文串的长度
    static int get_len(String s, int l, int r){
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r ++;
        }
        return r - l - 1;
    }

    public String longestPalindrome(String s) {
       if(s.length() < 1) return "";

       int n = s.length();
       //回文串两端的位置l r
       int l = - 1, r = n + 1;
       //以i为中心  回文串的最大长度
       int maxv = 0;
       for(int i = 0; i < n; i ++){
           //当回文子串是奇数时
           int len1 = get_len(s, i , i);

           //当回文子串是偶数时
           int len2 = get_len(s, i, i + 1);

           if(len1 > maxv){
               maxv = len1;
               l = i - len1 /2;
               r = i + len1 /2;
           }
           if(len2 > maxv){
               maxv = len2;
               //因为len2为偶数确认l和r有两个
               l = i - (len2 - 1)/2;
               r = i - len2/2;
           }
       }
       return s.substring(l, r + 1);
    }
}