Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. Tags: String

Try It!

Discussion

Video

Solution

Dynamic Programming Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False for j in range(n)] for i in range(n)]

        ans = ''
        # every string with one char is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
        
        # upper dp
        for start in range(n - 1, -1, -1):
            for end in range(start + 1, n):
                if s[start] == s[end]:
                    if end - start == 1 or dp[start + 1][end - 1]:
                        dp[start][end] = True
                        if end - start + 1 > len(ans):
                            ans = s[start:end + 1]
        return ans

Expand from middle solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_len = 0
        max_str = ''
        
        for i in range(len(s)):
            # odd
            j = i
            k = i
            while j >= 0 and k < len(s) and s[j] == s[k]:
                if k - j + 1 > max_len:
                    max_len = k - j + 1
                    max_str = s[j:k + 1]
                j -= 1
                k += 1
            # even
            j = i
            k = i + 1
            while j >= 0 and k < len(s) and s[j] == s[k]:
                if k - j + 1 > max_len:
                    max_len = k - j + 1
                    max_str = s[j:k + 1]
                j -= 1
                k += 1

        return max_str