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.

Example 1:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd" Output: "bb"

 

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        if length == 0:
            return ''
        if length == 1:
            return s

        if length == 2:
            if s[0] == s[-1]:
                return s
            else:
                return s[0]

        even_list = []
        odd_list = []

        for idx in range(1, length):
            # len(substring) : 2
            if s[idx - 1] == s[idx]:
                even_list.append([idx-1,idx,2])
            # len(substring) : 3
            if (idx != length - 1) and (s[idx - 1] == s[idx + 1]):
                odd_list.append([idx - 1, idx + 1,3])

        if (not even_list) and (not odd_list):
            return s[0]

        for even in even_list:
            while True:
                pre_length = even[-1]
                even = self.compute_palindrome(s,even)
                if pre_length == even[-1]:
                    break

        for odd in odd_list:
            while True:
                pre_length = odd[-1]
                odd = self.compute_palindrome(s,odd)
                if pre_length == odd[-1]:
                    break

        total = odd_list + even_list
        longgest_string_info = max(total, key=lambda x: x[2])

        return s[longgest_string_info[0]:longgest_string_info[1]+1]

    def compute_palindrome(self,s,star_end_length):
        if (star_end_length[0] != 0) and (star_end_length[1] != len(s) - 1):
            if s[star_end_length[0] - 1] == s[star_end_length[1] + 1]:
                star_end_length[0] -= 1
                star_end_length[1] += 1
                star_end_length[-1] += 2
        else:
            return star_end_length
        return star_end_length