Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:


Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:


Input: "cbbd"
Output: "bb"

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def longestPalindrome(self, s: str) -> str:
        

Solutions:
class Solution(object):

	def longestPalindrome(self, s):
		size = len(s)
		if size <= 1 or s == s[::-1]:
			return s
		(start, maxlen) = (0, 1)
		for idx in range(1, size):
			add2 = s[idx - maxlen - 1:idx + 1]
			if idx - maxlen - 1 >= 0 and add2 == add2[::-1]:
				start = idx - maxlen - 1
				maxlen += 2
				continue
			add1 = s[idx - maxlen:idx + 1]
			if add1 == add1[::-1]:
				start = idx - maxlen
				maxlen += 1
		return s[start:start + maxlen]


class Solution:

	def longestPalindrome(self, s):
		if not s:
			return ''
		(maxI, center, right) = (0, 0, 0)
		stL = self.addChar(s)
		pal = [0] * len(stL)
		for i in range(1, len(stL) - 1):
			currI = 2 * center - i
			if right > i:
				pal[i] = min(right - i, pal[currI])
			else:
				pal[i] = 0
			while stL[i + 1 + pal[i]] == stL[i - 1 - pal[i]]:
				pal[i] += 1
			if i + pal[i] > right:
				(center, right) = (i, i + pal[i])
		for i in range(1, len(stL) - 1):
			if pal[i] > pal[maxI]:
				maxI = i
		start = (maxI - 1 - pal[maxI]) // 2
		return s[start:start + pal[maxI]]

	def addChar(self, st):
		stLs = ['<']
		for c in st:
			stLs.extend([None, c])
		stLs.extend([None, '>'])
		return stLs


class Solution:

	def longestPalindrome(self, s):
		if s == s[::-1]:
			return s
		maxx = 1
		start = 0
		for i in range(1, len(s)):
			if i - maxx >= 0 and s[i - maxx:i + 1] == s[i - maxx:i + 1][::-1]:
				start = i - maxx
				maxx += 1
			elif i - maxx >= 1 and s[i - maxx - 1:i + 1] == s[i - maxx - 1:i + 1][::-1]:
				start = i - maxx - 1
				maxx += 2
		return s[start:start + maxx]


class Solution:

	def longestPalindrome(self, s):
		if s == s[::-1]:
			return s
		max_len = 1
		end = 0
		for i in range(1, len(s)):
			if i - max_len >= 0 and s[i - max_len:i + 1] == s[i - max_len:i + 1][::-1]:
				max_len = max_len + 1
				end = i
			elif i - max_len >= 1 and s[i - max_len - 1:i + 1] == s[i - max_len - 1:i + 1][::-1]:
				max_len = max_len + 2
				end = i
		return s[end - max_len + 1:end + 1]


class Solution:

	def longestPalindrome(self, s):
		if len(s) == 0:
			return 0
		maxLen = 1
		start = 0
		for i in range(len(s)):
			if i - maxLen >= 1 and s[i - maxLen - 1:i + 1] == s[i - maxLen - 1:i + 1][::-1]:
				start = i - maxLen - 1
				maxLen += 2
				continue
			if i - maxLen >= 0 and s[i - maxLen:i + 1] == s[i - maxLen:i + 1][::-1]:
				start = i - maxLen
				maxLen += 1
		return s[start:start + maxLen]