# Python3

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        # approach: iterate entire string and expand palindrome

        start = end = 0
        for i in range(len(s)):
            candidates = [(start, end)]
            candidates.append(self.expandPalindrome(s, i, i))
            if i + 1 < len(s) and s[i] == s[i+1]:
                candidates.append(self.expandPalindrome(s, i, i + 1))
            start, end = max(candidates, key=lambda x: x[1] - x[0])

        return s[start:end+1]

    def expandPalindrome(self, s, start, end):
        while start > -1 and end < len(s) and s[start] == s[end]:
            start -= 1
            end += 1

        return (start + 1, end - 1)