4
\$\begingroup\$

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

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

enter image description here

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

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

[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"))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.