5_Longest Palindromic Substring

5. Longest Palindromic Substring

Level: medium

Tag: string, dynamic programming

Question

Given a string s, find the longest palindromic substring in s. 
You may assume that the maximum length of s is 1000.

Note: A palindrome is a word, which reads the same backward as forward.

Idea: (expand around center, dynamic programming)

Loop from the beginning to the end. Take each letter be the center of the substring, and find maximum length substring centered by each letter.

There are two types of center:

• the letter is the center, such that the palindromic substring has odd number of letters

• the space on the right of the letter is the center, such that the palindromic substring has even number of letters

Complexity

• Time:$O(n^2)$

• Space:$O(1)$ if the length of the longest palindromic substring is constant.

Solution: (bottom-up)

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

        substring = ""

        # dynamic programming
        for i in range(len(s)):
            substring = max(substring, self.helper(s,i,i+1), self.helper(s,i,i), key=len)
        return substring    




        # helper function to get max palindromic substring expanding from s[l:r+1]
        # from center to outer letters
    def helper(self, s, l, r):
        """
        :type s: str
        :type l: num
        :type r: num
        :rtype: str
        """

        while l >= 0 and r <= len(s)-1 and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l+1:r]