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:
Please provide some insight as to how to modify the code to pass the time limit.
