```
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
if n <= 1:
return s
dp = [[False for i in range(n)] for j in range(n)]
startIdx = 0
endIdx = 0
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
startIdx = i
endIdx = i+1
maxLength = endIdx - startIdx + 1
# loop through each row and column and update dp
for i in range(n-2, -1, -1):
for j in range(i+2, n):
if dp[i+1][j-1] and s[i] == s[j]:
dp[i][j] = True
if j-i+1 <= maxLength:
continue
startIdx = i
endIdx = j
maxLength = j-i+1
return s[startIdx:(endIdx+1)]
```