Return to Revisions

As mentioned in the comments, you can check the Manacher's algorithm. Here's the link for python code of the algorithm: https://zkf85.github.io/2019/03/26/leetcode-005-longest-palindrome#approach-5-manachers-algorithm-on

This is the solution mentioned on the above link in python:

class Solution5:
def longestPalindrome(self, s: str) -> str:
    N = len(s) 
    if N < 2: 
        return s
    N = 2*N+1    # Position count 
    L = [0] * N 
    L[0] = 0
    L[1] = 1
    C = 1     # centerPosition 
    R = 2     # centerRightPosition 
    i = 0    # currentRightPosition 
    iMirror = 0     # currentLeftPosition 
    maxLPSLength = 0
    maxLPSCenterPosition = 0
    start = -1
    end = -1
    diff = -1

    for i in range(2, N): 
        # get currentLeftPosition iMirror for currentRightPosition i 
        iMirror = 2*C-i 
        L[i] = 0
        diff = R - i 
        # If currentRightPosition i is within centerRightPosition R 
        if diff > 0: 
            L[i] = min(L[iMirror], diff) 

        # Attempt to expand palindrome centered at currentRightPosition i 
        # Here for odd positions, we compare characters and 
        # if match then increment LPS Length by ONE 
        # If even position, we just increment LPS by ONE without 
        # any character comparison 
        try:
            while ((i + L[i]) < N and (i - L[i]) > 0) and \ 
                (((i + L[i] + 1) % 2 == 0) or \ 
                (s[(i + L[i] + 1) // 2] == s[(i - L[i] - 1) // 2])): 
                L[i]+=1
        except Exception as e:
            pass
            
        if L[i] > maxLPSLength:        # Track maxLPSLength 
            maxLPSLength = L[i] 
            maxLPSCenterPosition = i 

        # If palindrome centered at currentRightPosition i 
        # expand beyond centerRightPosition R, 
        # adjust centerPosition C based on expanded palindrome. 
        if i + L[i] > R: 
            C = i 
            R = i + L[i] 

    start = (maxLPSCenterPosition - maxLPSLength) // 2
    end = start + maxLPSLength - 1
    return s[start:end+1]

The above approach is the most optimized approach and it's time complexity is O(n) which I think is the best.

I hope this helps you!