Longest Palindromic Substring

Java

class Solution {
    public String longestPalindrome(String s) {
        char[] chars = convertString(s);
        int[] counts = new int[chars.length];
        int center = 0;
        int rightIndex = 0;
        for (int i = 1; i < chars.length - 1; i++) {
            int leftIndex = 2 * center - rightIndex;
            counts[i] = rightIndex > i ? Math.min(rightIndex - i, counts[leftIndex]) : 0;
            while (chars[i + counts[i] + 1] == chars[i - 1 - counts[i]]) {
                counts[i]++;
            }
            if (i + counts[i] > rightIndex) {
                center = i;
                rightIndex = i + counts[i];
            }
        }
        int maxLen = 0;
        for (int i = 1; i < counts.length - 1; i++) {
            if (counts[i] > maxLen) {
                maxLen = counts[i];
                center = i;
            }
        }
        return s.substring((center - 1 - maxLen) / 2, (center - 1 - maxLen) / 2 + maxLen);
    }
    
    private char[] convertString(String s) {
        int len = s.length();
        char[] result = new char[len * 2 + 3];
        result[0] = '^';
        for (int i = 1, j = 0; i < result.length - 1; i++) {
            result[i] = (i & 1) == 1 ? '#' : s.charAt(j++);
        }
        result[result.length - 1] = '$';
        return result;
    }
}

Python

class Solution:
    def longestPalindrome(self, s):
        if s == None or len(s) == 0:
            return ""
        longest = 1
        start = 0
        end = 0
        i = 1
        while 2 * len(s) - 1 - i > longest:
            if i & 1:
                left = (i - 1) // 2
                right = left + 1
            else:
                left = i // 2 - 1
                right = left + 2
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # left和right此时为试探失败的一对位置 
            if right - left - 1 > longest:
                longest = right - left - 1
                start = left + 1
                end = right - 1
            i += 1
        return s[start: end + 1]