5. Longest Palindromic Substring

# Medium

Solution 1: radical extend

Check the longest palindromic substring when central element is from s[0] to s[n]. Use two pointers left and right to track the two edge element of the palindromic.

从第一个到最后一个元素，尝试作为中心的元素，最长回文字符串分奇数和偶数。

Python

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        # edge case
        if len(s) <= 1:
            return s
        
        # regular case
        res = []
        res_len = 0
        for i in range(len(s)):
            left, right = i, i
            # if the longest palindromic substring is odd, 奇数
            while left >=0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > res_len:
                    res = s[left:right+1]
                    res_len = right - left + 1
                left -= 1
                right += 1
            
            # if the longest palindromic substring is even，偶数
            left, right = i, i+1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > res_len:
                    res = s[left:right+1]
                    res_len = right - left + 1
                left -= 1
                right += 1
                
        return res

Time complexity = $O(n^2)$ , space complexity = $O(n)$ .

Solution 2: Dynamic Programming

Use dp[i][j] to record from i to j is Palion or not. Key idea is: if s[i] = s[j] and dp[i+1][j-1] is Palion, then dp[i][j] is Palion.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False]*len(s) for i in range(len(s))]
        output  = ''
        
        for end in range(len(s)):
            for start in range(end+1):
                if s[start] == s[end]:
                    l = end - start + 1
                    if l < 3 or dp[start+1][end-1]:
                        dp[start][end] = True
                    
                    if l > len(output) and dp[start][end]:
                        output = s[start:end+1]
        return output

T = $O(n^2)$ , S = $O(n^2)$