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 &quot;substring&quot; must be contiguous, and in case of ties the first such substring should be returned.

Example:
Input : &quot;aaaabaaa&quot;
Output : &quot;aaabaaa&quot;


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 &quot;&quot;.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 &lt; len(cleaned)-1):
            end_index = start_index
            while (end_index &lt; len(cleaned)):
                end_index +=1
                if self.is_palindrome(cleaned[start_index:end_index]):
                    if len(cleaned[start_index:end_index]) &gt; max:
                        longest = cleaned[start_index:end_index]
                        max = end_index-start_index

            start_index +=1
        return longest


s = Solution()
print(s.longestPalindrome(&quot;abbcccaaadaaakl&quot;))

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.
[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()
print(s.longest_palindrome("abbcccaaadaaakl"))


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

print(lp("abbcccaaadaaakl"))