class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        bool dp = [[False]*1000 for x in range(1000)]
        n = len(s)
        maxLen = 1
        maxStart = 0

        # dp[i][i] = True
        for i in range(n):
            dp[i][i] = True

        # dp[i][i+1] = True if s[i] == s[i+1]
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                maxLen = 2
                maxStart = i

        # dp[i][j] = True if s[i]==s[j] and dp[i+1][j-1] == True
        for length in range(3,n+1):
            for i in range(n-length+1):
                j = i+length-1
                if s[i] == s[j] and dp[i+1][j-1] == True:
                    dp[i][j] = True
                    maxLen = length
                    maxStart = i
        return s[maxStart,maxStart+maxLen]

public class Solution {
    private int lo;
    private int maxLen;

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        for(int i=0; i<len-1; i++){
            // 奇数长度
            extentPalindrome(s, i, i);
            // 偶数长度
            extentPalindrome(s, i, i+1);
        }
        return s.substring(lo, lo+maxLen);
    }

    public void extentPalindrome(String s, int start, int end){
        // start, end　之间一定维持着palindrome
        while(start >=0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            // 持续向两面扩张
            start--;
            end++;
        }

        // 注意: 此时end,start已经过了
        if(maxLen < end-start-1){
            maxLen = end-start-1;
            lo = start+1;
        }
    }
}