leetcode-5 Longest Palindromic Substring

# Given a string s, return the longest palindromic substring in s.
# 
# Example 1:
# Input: s = "babad"
# Output: "bab"
# Explanation: "aba" is also a valid answer.
# 
# Example 2:
# Input: s = "cbbd"
# Output: "bb"
# 
# Constraints:
# 1 <= s.length <= 1000
# s consist of only digits and English letters.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]

        for i in range(n):
            dp[i][i]=True

        ans = s[0]

        for j in range(n):
            for i in range(j):
                if s[i]==s[j] and (j==i+1 or dp[i+1][j-1]):
                    dp[i][j]=True
                    if j - i + 1 > len(ans):
                        ans = s[i : j+1]
        return ans