# Longest Palindromic Substring better approach

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


# 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]

• method names are to be in snake_case” do you mean idiomatic python, e.g. per the PEP 8 style guide? – Sᴀᴍ Onᴇᴌᴀ Sep 16 '19 at 6:16
• Yes @SᴀᴍOnᴇᴌᴀ, many of my suggestions were based off that guide, and some other practices. – Linny Sep 16 '19 at 6:49
• Okay would you mind updating your statement, to be explicit about what is valid verses what is idiomatic? – Sᴀᴍ Onᴇᴌᴀ Sep 16 '19 at 18:38
• @SᴀᴍOnᴇᴌᴀ Updated accordingly. Thanks again. – Linny Sep 16 '19 at 19:41

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!

• Welcome to Code Review! A link to a solution is welcome, but please ensure your answer is useful without it: add context around the link so your fellow users will have some idea what it is and why it’s there, then quote the most relevant part of the page you're linking to in case the target page is unavailable. Answers that are little more than a link may be deleted. – Sᴀᴍ Onᴇᴌᴀ Sep 5 '19 at 23:41
• Fix indentation – user203258 Sep 17 '19 at 11:57