Idea: We follow the intuition that P(Start, End) == (P(Start + 1, End - 1) and S[Start] == S[End]) and store these results in the DP table. We only need to check to update the max string if we've updated the table.

```
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
n = len(s)
maxFinal = s[0]
dp = [[0]*n for _ in range(n)]
for end in range(n):
dp[end][end] = 1
for start in range(end):
if (dp[start+1][end-1] == 1 or start + 1 > end - 1) and s[start] == s[end]:
dp[start][end] = 1
if (end - start + 1) > len(maxFinal):
maxFinal = s[start:end+1]
return maxFinal
```