My idea is quite simple: check whether each substring is a Palindrome using two pointers: start and end. Pointer start is from 0, and end is from len(s) to 0.
I have two optimizations.
One is 'end' will alway larger than the previous end 'prevend'.
Because start increases, if end < prevend, you won't get a longer palindrome
One is if end == len(s), then stop. Because you find a Palindrome from start to end.
I use the second one to avoid test case like("aaaa...") case. However, I still has TLE.
Can anyone help me with this?
The following is my code.
class Solution(object): def isPalindrome(self, s, start, end): #Test s[start:end] is Palindrome or not. if start > end : return False i = start j = end - 1 while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True def longestPalindrome(self, s): """ :type s: str :rtype: str """ start = 0 longPalindrom = "" maxlen = 0 preend = 0 # save previous end while start < len(s): end = len(s) # find longest palindrome begins s[start] while not self.isPalindrome(s, start, end) and end > preend: end -= 1 preend = end if maxlen < end - start: longPalindrom = s[start:end] maxlen = end - start if end == len(s): # second optimization break start += 1 return longPalindrom