密码截取

和Leetcode 5 最长回文字是一个题，暴力解采用双指针从两侧向中心搜索，复杂度可达O（n^3）。这里我们采用中心扩散的做法，把复杂度降到O（n^2）。
所谓中心扩散，就是选定一个值，然后向左右扩散。我们可以发现，回文串有两种，一种是aabb，中心在ab之间；另一种是aacbb，中心为c。我们可以写一个方法，通过给left和right传入不同的初始index来实现这两种情况。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            int max = 0;
            for(int i = 0; i < str.length() - 1; i++){
                //aabaa的情况
                max = Math.max(max,longestPalindrome(str,i,i));
                //aabbaa的情况
                max = Math.max(max,longestPalindrome(str,i,i+1));
            }
            System.out.println(max);
        }
    }

    public static int longestPalindrome(String s, int left, int right){
        int len = 0;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            len = right - left + 1;
            left--;
            right++;
        }
        return len;
    }
}