Longest Palindromic Substring better approach

Question

I have encountered to this question and applied a brute force algorithm off top of my head and couldn't find a better optimized solution.

I was hoping I could get some insight to implement a better optimized code in terms of complexity. My solution has \$O(n^2)\$ time and space complexity.

class Solution:

    def longestPalindrome(self, s: 'str') -> 'str':
        if s=="":
            return ""
        else:
           ## Find all the substrings
            arr=[]
            for i in range(len(s)):
                char = s[i]
                arr.append(char)
                for j in range(i+1, len(s)-1):
                    char+=s[j]
                    arr.append(char)

            ##Find the palindrome with a longest length
            max_length = 0
            for j in range(len(arr)):
                if self.isPalindrome(arr[j]):
                    if len(arr[j]) > max_length:
                        max_length = len(arr[j])
                        index = arr[j]
            return index


    def isPalindrome(self,s:'str')->'str':
        if s == s[::-1]:
            return True

Answer 1

Unnecessary else after return

In the body of an if, if you end up returning something in that body, an else is not required. A return will exit the body of the function, so the code in the else won't be run. So, you can simply move the code in the else to the outside, after the if. This may have been confusing, but take a look at the updated code to see what I'm talking about.

enumerate()

Instead of using range(len()), use enumerate(). This will allow you to access both the index and the value at that position, and enumerate works for other iterables as well. It's useful here because instead of writing arr[j] over and over, you can simply write value, which is the value at arr[j].

_ for unused loop variables

Also touching on enumerate- When you only want to use one of the values (in your code, you have both cases present), use an _ in that place. This indicates to you and other readers that that variable is to be ignored, and isn't necessary.

Parameter Spacing

When using : in parameters, make sure there is exactly one space after the :.

Operator Spacing

Make sure to space out your operators when assigning and performing arithmetic on variables. It makes it much easier to read, and looks nicer.

return True

Instead of explicitly returning true if the if condition is true, simply return that condition. It will return the boolean value that is returned from that condition.

function_naming

I know you can't change the function names (assuming this is coming from a code challenge website), but remember that method names are to be in snake_case, not camelCase or PascalCase. This is in reference to PEP-8 Method Naming Guidelines. Thanks to @SᴀᴍOnᴇᴌᴀ for pointing this out to me.

Updated Code

class Solution:

    def longestPalindrome(self, s: 'str') -> 'str':
        if s == "":
            return ""
        ## Find all the substrings
        arr = []
        for i, value in enumerate(s):
            char = value
            arr.append(char)
            for j in range(i + 1, len(s) - 1):
                char += s[j]
                arr.append(char)

        ##Find the palindrome with a longest length
        max_length = 0
        for _, value  in enumerate(arr):
            if self.isPalindrome(value):
                if len(value) > max_length:
                    max_length = len(value)
                    index = value
        return index


    def isPalindrome(self, s: 'str')->'str':
        return s == s[::-1]

Answer 2

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!