# Share a nlogn solution, but TLE in python; however, I think i would be fine if in C.

• ``````def suffix_array(s):
return [s[i:] for i in xrange(len(s)-1)]

def count_prefix(a, b):
if a[1] == b[1]:
return 0

cnt = 0
for i in range(min(len(a[0]), len(b[0]))):
if a[0][i] == b[0][i]:
cnt += 1
return cnt

class Solution:
# @return a string
def longestPalindrome(self, s):
n = len(s)
S = s
R = s[::-1]
s_sfx = zip(suffix_array(S), [0] * n)
r_sfx = zip(suffix_array(R), [1] * n)

lst = sorted(s_sfx + r_sfx, key=lambda t: t[0])

m_len = 0
m_str = ''
for i in range(len(lst)-1):
l = count_prefix(lst[i], lst[i+1])
if l > m_len:
m_len = l
m_str = lst[i][0][:m_len]

return m_str

if __name__ == '__main__':
print Solution().longestPalindrome(raw_input().strip())
``````

if n^2 solution can pass the test in C+/Java, I suggest to loose the time limit when code written in Python :-)

• Questions about code you've written must describe the specific problem clearly, elaborate thoughts based on code and preserve code formatting as well. Please read the FAQ for more info.

• The current version of the algorithm has a bug in it:

``````def count_prefix(a, b):
if a[1] == b[1]:
return 0

cnt = 0
for i in range(min(len(a[0]), len(b[0]))):
if a[0][i] == b[0][i]:
cnt += 1
return cnt
``````

Should probably be like this:

``````def count_prefix(a, b):
if a[1] == b[1]:
return 0

cnt = 0
for i in range(min(len(a[0]), len(b[0]))):
if a[0][i] == b[0][i]:
cnt += 1
else:
return cnt
return cnt
``````

This makes it work a bit better, but it still fails on the following input for me:

``````abcxxkcba
``````

The output is "abc", but it should actually be "xx". "abc" is not a palindrome.

Maybe I made a mistake somewhere.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.