Improving time complexity of finding the longest palindrome in Python

The Longest Palindromic Substring challenge from InterviewBit:

Given a string S, find the longest palindromic substring in S.

where a "substring" must be contiguous, and in case of ties the first such substring should be returned.

Example:

Input : "aaaabaaa"
Output : "aaabaaa"


My code:

class Solution:
# @param A : string
# @return a strings
def clean_string(self, string):
result = []
str_list = string.split()
for word in str_list:
result.append(''.join(ch for ch in word if ch.isalnum()))
return "".join(result).lower()

def is_palindrome(self, string):
if len(string)==1:
return True
if string[::-1]==string:
return True
return False

def longestPalindrome(self, A):
if len(A)==1:
return A
cleaned = self.clean_string(A)
start_index = 0
max = -1
longest = None
while (start_index < len(cleaned)-1):
end_index = start_index
while (end_index < len(cleaned)):
end_index +=1
if self.is_palindrome(cleaned[start_index:end_index]):
if len(cleaned[start_index:end_index]) > max:
longest = cleaned[start_index:end_index]
max = end_index-start_index

start_index +=1
return longest

s = Solution()


My code passes all the tests except for the time limit:

Please provide some insight as to how to modify the code to pass the time limit.

• Remember though, the points don't matter! – Insane Jun 1 '16 at 5:23
• haha thanks except I am not passing some of the testcases due to exceeding time limits! – Mona Jalal Jun 1 '16 at 5:27

[EDIT] I believe the time-out occurs if you are not fast enough typing your code in the website where this challenge is posted. I believe it is not about optimizing code to run faster, but how quickly you can come up with working code. The following is still true in regards to Code Review:

I might not have all improvements, but here are some I would do

from re import sub


you could rewrite this function:

def clean_string(self, string):
return sub(r'[^a-zA-Z0-9]', '', string)


and rewrite this function:

def is_palindrome(self, string):
return string[::-1]==string


Then the first if statement in def longestPalindrome(self, A) would change too:

def longestPalindrome(self, A):
if self.is_palindrome(A):
return A


No need for this:

    if len(A)==1:
return A


You can replace the while loops with for loops, something like this:

def longestPalindrome(self, A):
if self.is_palindrome(A):
return A
cleaned = self.clean_string(A)
for l in range(len(cleaned)-1,0,-1):  ## l = lenght to check high to low
for i in range(0, len(cleaned)-l+1):  ## i is position in A to check
if self.is_palindrome(A[i:l+i]):
return A[i:l+i]
return None


Those changes would be faster then your original code, but I did not do any scientific tests, so the obligatory: "YMMV"

[EDIT]

In fact you can shorten the code further:

from re import sub

class Solution:

def longest_palindrome(self, a):
if a[::-1] == a:
return a
a = sub(r'[^a-zA-Z0-9]', '', a)
for l in range(len(a)-1, 0, -1):
for i in range(0, len(a)-l+1):
if a[i:l+i][::-1] == a[i:l+i]:
return a[i:l+i]
return None

s = Solution()


and you really don't need a class here:

from re import sub

def lp(a):
if a[::-1] == a:
return a
a = sub(r'[^a-zA-Z0-9]', '', a)
for l in range(len(a)-1, 0, -1):
for i in range(0, len(a)-l+1):
if a[i:l+i][::-1] == a[i:l+i]:
return a[i:l+i]
return None