[LeetCode] Longest Palindromic Substring

 

 

Problem

 

 

---

 

Solution

 

Start from the center of the string, and expand to left and right until the characters at those positions are not the same.

 

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s is None or len(s) < 1:
            return ""
        start = 0
        end = 0
        for i in range(len(s)):
            len1 = self.expandCenter(s, i, i)
            len2 = self.expandCenter(s, i, i+1)
            length = max(len1, len2)
            if end - start < length:  # if current recorded length is shorter, update it
                # subtract 1 in case the palindrome has an even length
                # (i.e. starting position was i, i+1)
                start = i - (length - 1)/2
                end = i + length/2
            
        return s[start:end+1]
            
    
    def expandCenter(self, s, left, right):
        while 0 <= left and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
            
        return right - left - 1  # subtract 1 since right was already updated before while check