腾讯经常解答十个真实算法题：最高的回文子串

给你一个字符串s，找出s中最高的回文子串。

例一：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

这道题可以用中心展开法来解答，从中心开始，向两侧扩散来评价回文串。

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是回文串的长度可以是奇数，也可以是偶数，所以还需要添加一步：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和s[i+1] 为中心的回文串
    更新答案

完整代码如下：

class Solution {
    public String longestPalindrome(String s) {

        if(s==null|| s.length()<2){
             return s;
        }

        String result ="";
        for(int i=0;i<s.length();i++){
            String r1 = subLongestPalindrome(s,i,i);
            String r2 = subLongestPalindrome(s,i,i+1);
            String tempMax= r1.length()>r2.length()? r1 :r2;
            result = tempMax.length()> result.length()?tempMax:result;
            
        }
        return result;

    }

    private String subLongestPalindrome(String s,int l,int r){
        while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }

        return s.substring(l+1,r);
    }
}