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"

def longestPalindrome(self, s: str) -> str:
	dp = [[-1 for _ in range(len(s))] for _ in range(len(s))]
	def checkpalindrome(i,j):
		if i >= j:
			return True

		if dp[i][j] != -1:
			return dp[i][j] 
		
		if s[i] == s[j]:
			dp[i][j] = checkpalindrome(i+1, j-1)
			return dp[i][j]

		dp[i][j] = False
		return dp[i][j]
	
	maxLen = 0
	sp = 0
	l = len(s)
	for i in range(l):
		for j in range(i, l):
			if checkpalindrome(i,j) == True and (j-i+1) > maxLen:
				maxLen = j - i + 1
				sp = i
	return s[sp:sp+maxLen]