5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

 

Given a string s, return the longest palindromic

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        r: int = 0
        c: int = 0

        maxLen = 1
        result = s[0]

        s = '#' + '#'.join(s) + '#'
        dp = [0 for _ in range(len(s))]

        for idx in range(len(dp)):
            if idx <= r:
                dp[idx] = min(dp[2 * c - idx], r - idx)
            # get dp[idx] value
            while idx - dp[idx] - 1 >=0 and idx + dp[idx] + 1< len(s) and s[idx - dp[idx] - 1] == s[idx + dp[idx] + 1]:
                dp[idx]+=1
            if dp[idx] > r - idx:
                r = dp[idx] + idx
                c = idx
            
            if dp[idx] > maxLen:
                maxLen = dp[idx]
                result = s[idx-dp[idx]:idx+dp[idx]+1]
                
        return result.replace('#','')

 

dp[n] = radius of the pelindrom's around index(=n)

r = last index of the currently longest pelindrom

c = index of the center of the currently longest pelindrom

 

I first thought brute force solution as iterting string. In bad case, It can be O(n^2) time complexity. This is why I tried to think of another solution. But I couldn't think of it until the end.

 

I found a solution using Manacher's Algorithm, which can solve in O(n).