【字符串】最长回文子串 ( 中心线枚举算法 )

class Solution {
    /**
     * @param s: 输入字符串
     * @return: 返回最长回文子串
     */
    public String longestPalindrome(String s) {
        if (s == null) {
            return null;
        }

        String longest = "";
        for (int i = 0; i < s.length(); i ++) {
            // 回文子串字符个数是奇数个
            String oddPalindrome = getPalindrome(s, i, i);
            if (longest.length() < oddPalindrome.length()) {
                longest = oddPalindrome;
            }

            // 回文子串字符个数是偶数个
            String evenPalindrome = getPalindrome(s, i, i + 1);
            if (longest.length() < evenPalindrome.length()) {
                longest = evenPalindrome;
            }
        }

        return longest;
    }

    private String getPalindrome(String s, int left, int right) {
        /*
            left right 两个指针分别指向中心线两侧的元素索引
            如果回文子串有奇数个字符, 中心线是字符, left = right = 中心线索引
            如果回文子串有偶数个字符, 中心线是空隙, left + 1 = right
         */
        while(left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}

class Main {
    public static void main(String[] args) {
        String palindrome = new Solution().longestPalindrome("mabcban");
        System.out.println(palindrome);
    }
}