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  max:
                        longest = cleaned[start_index:end_index]
                        max = end_index-start_index

            start_index +=1
        return longest

s = Solution()
print(s.longestPalindrome("abbcccaaadaaakl"))

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"))

StackExchange Code Review Q#129821, answer score: 2