# Python Dynamic Programming solution but exceeds Time Limit, please tell me how to improve.

• '''

``````def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = len(s)
p = [[True] * l for x in range(l)]
t = 0
max = 0
ri = 0
rj = 0
for j in range(l):
for i in range(l - j):
if t == 1:
p[i][i + t] = (s[i] == s[i + t])
elif t >= 2:
p[i][i + t] = p[i + 1][ i + t - 1] and (s[i] == s[i + t])
if p[i][i + t] and t + 1 > max:
max = t + 1
ri = i
rj = i + t
t += 1
return s[ri:(rj + 1)]
``````

'''
My algorithm is the same with the approach #3 and I think there is no logical error, but it turns out it exceeds the time limit, I have tried multiple ways to improve the speed but still in vain, can anyone help me handle it?

• you don't have to check every case in the loop.
When you know 'ab' is not a palindrome, then every string centered on 'ab', for example 'cabc' and 'xaby', is not a palindrome. You can then move on to next center. this would help trim a large part of the problem space.

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