Leetcode 5: Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Code:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) == 0:
            return ""

        start = 0
        max_len = 1        

        for i in xrange(len(s)):
            if i-max_len-1 >=0 and s[i-max_len-1:i+1] == s[i-max_len-1:i+1][::-1]:
                start = i - max_len - 1
                max_len = max_len + 2
                continue

            if i-max_len >=0 and s[i-max_len:i+1] == s[i-max_len:i+1][::-1]:
                start = i - max_len
                max_len = max_len + 1

        return s[start:start+max_len]

Idea: 

The optimal solution is O(N^2) time complex. So nothing very special. You traverse every position in `s`. You always compare if s[i-max_len-1:i+1] reads same as s[i-max_len-1:i+1][::-1]. See the picture below.

We first test whether s[i-max_len-1:i+1] is palindrome then s[i-max_len:i+1] because the next palindrome can possibly be longer than the previous palindrome by at most 2 characters.