Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 ≤ i ≤ j < len(S). Palindrome string: A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S. Incase of conflict, return the substring which occurs first ( with the least starting index ).
Example 1:
Input:
S = "aaaabbaa"
Output:
aabbaa
Explanation:
The longest palindrome string present in
the given string is "aabbaa".
Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestPalindrome() which takes string S as input parameters and returns longest pallindrome present in string.
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{4}

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def longestPalindrome(self, S):

        # code here

Solutions:
class Solution:

	def longestPalindrome(self, S):
		s = S[0]
		for i in range(len(S)):
			for j in range(i + 1, len(S) + 1):
				k = S[i:j]
				if k == k[::-1] and len(k) > 1:
					if len(k) > len(s):
						s = k
		return s


class Solution:

	def longestPalindrome(self, S):
		string = []
		for i in S:
			string.append('@')
			string.append(i)
		string.append('@')
		length = [1] * len(string)
		(left, right) = (1, 1)
		for i in range(1, len(string)):
			length[i] = max(1, min(right - i, length[left + right - i]))
			while i + length[i] < len(string) and i - length[i] >= 0 and (string[i - length[i]] == string[i + length[i]]):
				length[i] += 1
			if i + length[i] > right:
				left = i - length[i]
				right = i + length[i]
		maxi = max(length)
		maxIndex = length.index(maxi)
		maxi -= 1
		ind = 0
		res = []
		for i in string[maxIndex - maxi:maxIndex + maxi]:
			if ind % 2 == 1:
				res.append(i)
			ind += 1
		return ''.join(res)


class Solution:

	def longestPalindrome(self, S):
		longest = ''
		len_s = len(S)
		for i in range(0, len(S)):
			for j in range(i + 1, len(S) + 1):
				if S[i:j] == S[-(len_s - j + 1):-(len_s - i + 1):-1]:
					if len(S[i:j]) > len(longest):
						longest = S[i:j]
		return longest


class Solution:

	def longestPalindrome(self, S):
		pal = ''
		pal_len = 1
		pal_list = []
		n = len(S)
		for i in range(n + 1):
			for j in range(n + 1):
				pal = S[i:j]
				if pal == pal[::-1]:
					pal_list.append(pal)
		longest = sorted(pal_list, key=len, reverse=True)
		return longest[0]


class Solution:

	def longestPalindrome(self, S):
		li = []
		for i in range(len(S)):
			for j in range(i + 1, len(S) + 1):
				li.append(S[i:j])
		ans = []
		for i in li:
			if i == i[::-1]:
				ans.append(i)
		return max(ans, key=len)


class Solution:

	def longestPalindrome(self, S):
		l = [S[i:j] for i in range(len(S)) for j in range(i + 1, len(S) + 1)]
		m = []
		for i in l:
			if i == i[::-1]:
				m.append(i)
		return max(m, key=len)


class Solution:

	def __init__(self):
		self.reslen = 0
		self.res = ''

	def expand(self, l, r):
		while l >= 0 and r < len(S) and (S[l] == S[r]):
			if r - l + 1 > self.reslen:
				self.res = S[l:r + 1]
				self.reslen = r - l + 1
			l -= 1
			r += 1

	def longestPalindrome(self, S):
		for i in range(len(S)):
			self.expand(i, i)
			self.expand(i, i + 1)
		return self.res


class Solution:

	def longestPalindrome(self, S):
		(le, re) = (float('-inf'), [0, 0])
		for i in range(len(S)):
			l = r = i
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				l -= 1
				r += 1
			window = r - l + 1 - 2
			if window > le:
				le = window
				res = [l + 1, r]
			l = i
			r = i + 1
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				l -= 1
				r += 1
			window = r - l + 1 - 2
			if window > le:
				le = window
				res = [l + 1, r]
		return S[res[0]:res[1]]


from collections import defaultdict

class Solution:

	def longestPalindrome(self, S):
		d = defaultdict(list)
		n = len(S)
		maxlen = 0
		ans = ''
		for i in range(n):
			d[S[i]] += [i]
			for j in d[S[i]]:
				val = S[j:i + 1]
				if val == val[::-1] and maxlen < i - j + 1:
					maxlen = i - j + 1
					ans = val
		return ans


class Solution:

	def longestPalindrome(self, s):
		(n, m, x, y) = (len(s), 0, -1, -1)
		l = [[0] * n for i in range(n)]
		for i in range(n):
			for j in range(n - i):
				if i == 0:
					l[j][j] = 1
				elif i == 1:
					if s[j] == s[j + 1]:
						l[j][j + 1] = 2
				else:
					k = j + i
					if s[j] == s[k] and l[j + 1][k - 1]:
						l[j][k] = l[j + 1][k - 1] + 2
				if l[j][j + i] > m:
					(m, x, y) = (l[j][j + i], j, j + i)
		return s[x:y + 1]


class Solution:

	def longestPalindrome(self, s):
		res = ''
		resLen = 0
		for i in range(len(s)):
			(l, r) = (i, i)
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				if r - l + 1 > resLen:
					res = s[l:r + 1]
					resLen = r - l + 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				if r - l + 1 > resLen:
					res = s[l:r + 1]
					resLen = r - l + 1
				l -= 1
				r += 1
		return res


class Solution:

	def longestPalindrome(self, s):
		if not s:
			return ''
		res = ''
		for i in range(len(s)):
			p1 = self.isPalindrome(s, i, i)
			p2 = self.isPalindrome(s, i, i + 1)
			if len(p1) > len(res):
				res = p1
			if len(p2) > len(res):
				res = p2
		return res

	def isPalindrome(self, s: str, l: int, r: int) -> str:
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			l -= 1
			r += 1
		return s[l + 1:r]


class Solution:

	def longestPalindrome(self, s):
		op = -10 ** 9
		oplen = 0
		n = len(s)
		for i in range(n):
			l = i
			r = i
			c = s[i]
			while l >= 0 and r < n and (s[l] == s[r]):
				if l != r:
					c = s[l] + c + s[r]
				l -= 1
				r += 1
			clen = len(c)
			if clen > oplen:
				oplen = clen
				op = c
			l = i
			r = i + 1
			c = ''
			while l >= 0 and r < n and (s[l] == s[r]):
				c = s[l] + c + s[r]
				l -= 1
				r += 1
			clen = len(c)
			if clen > oplen:
				oplen = clen
				op = c
		return op


class Solution:

	def longestPalindrome(self, S):
		x = len(S)
		length = 0
		res = ''
		for i in range(x):
			(l, r) = (i, i)
			while l >= 0 and r < x and (S[l] == S[r]):
				if r - l + 1 > length:
					res = S[l:r + 1]
					length = r - l + 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < x and (S[l] == S[r]):
				if r - l + 1 > length:
					res = S[l:r + 1]
					length = r - l + 1
				l -= 1
				r += 1
		return res


class Solution:

	def longestPalindrome(self, S):
		resL = resR = 0
		for i in range(len(S)):
			l = r = i
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				if r - l + 1 > resR - resL + 1:
					resL = l
					resR = r
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				if r - l + 1 > resR - resL + 1:
					resL = l
					resR = r
				l -= 1
				r += 1
		return S[resL:resR + 1]


class Solution:

	def longestPalindrome(self, S):
		n = len(S)
		start = 0
		maxlen = 1
		for i in range(n):
			for j in range(i, n):
				flag = 1
				for k in range((j - i) // 2 + 1):
					if S[i + k] != S[j - k]:
						flag = 0
						break
				if flag != 0 and j - i + 1 > maxlen:
					start = i
					maxlen = j - i + 1
		end = start + maxlen - 1
		a = ''
		for i in range(start, end + 1):
			a += S[i]
		return a


class Solution:

	def longestPalindrome(self, S):
		s = S
		n = len(s)
		if n <= 1:
			return s
		ns = ''
		for i in range(n):
			ns = ns + '*' + s[i]
		ns = ns + '*'
		n = len(ns)
		LPS = [0] * n
		c = 1
		r = 2
		imirr = 0
		maxlpslength = 0
		maxlpscenter = 1
		start = 0
		for i in range(1, n):
			if i <= r:
				imirr = c - i
				LPS[i] = LPS[imirr]
			while (i + LPS[i] + 1 < n and i - LPS[i] - 1 >= 0) and ns[i + LPS[i] + 1] == ns[i - LPS[i] - 1]:
				LPS[i] += 1
			if maxlpslength < LPS[i]:
				maxlpslength = LPS[i]
				maxlpscenter = i
				r = i + LPS[i]
				c = i
				start = (2 * c - r) // 2
		return s[start:start + maxlpslength]


class Solution:

	def longestPalindrome(self, s):
		n = len(s)
		z = s[::-1]
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		max_len = 0
		max_end = 0
		for i in range(n):
			for j in range(n):
				if s[i] == z[j]:
					if i == 0 or j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i - 1][j - 1] + 1
				if dp[i][j] > max_len:
					if i - dp[i][j] + 1 == n - j - 1:
						max_len = dp[i][j]
						max_end = i
		return s[max_end - max_len + 1:max_end + 1]


class Solution:

	def longestPalindrome(self, s):
		substr = ''
		maxlen = 0
		for i in range(len(s)):
			(l, r) = (i, i)
			while l >= 0 and r < len(s) and (s[l] == s[r]):
				if r - l + 1 > maxlen:
					substr = s[l:r + 1]
					maxlen = r - l + 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r <= len(s) - 1 and (s[l] == s[r]):
				if r - l + 1 > maxlen:
					substr = s[l:r + 1]
					maxlen = r - l + 1
				l -= 1
				r += 1
		return substr


class Solution:

	def longestPalindrome(self, S):
		m = len(S)
		s1 = S[::-1]
		n = m
		dp = [[-1] * (m + 1) for _ in range(n + 1)]
		for i in range(m + 1):
			dp[i][i] = 1
		start = 0
		flag = 0
		maxlength = 1
		for i in range(m - 1):
			if S[i] == S[i + 1]:
				dp[i][i + 1] = 1
				if flag == 0:
					maxlength = 2
					start = i
					flag = 1
		for k in range(3, m + 1):
			for i in range(m - k + 1):
				j = i + k - 1
				if S[i] == S[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
					if maxlength < k:
						maxlength = k
						start = i
		ans = ''
		for i in range(start, start + maxlength):
			ans += S[i]
		return ans


class Solution:

	def longestPalindrome(self, s):
		d = [[0 for x in range(len(s))] for y in range(len(s))]
		i = 0
		for i in range(len(s)):
			d[i][i] = True
		start = 0
		lenI = 1
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				d[i][i + 1] = True
				if lenI < 2:
					start = i
				lenI = 2
		k = 3
		max = lenI
		n = len(s)
		while k <= n:
			i = 0
			while i < n - k + 1:
				j = k + i - 1
				if d[i + 1][j - 1] and s[i] == s[j]:
					d[i][j] = True
					if k > max:
						max = k
						start = i
				i = i + 1
			k = k + 1
		return S[start:start + max]


class Solution:

	def longestPalindrome(self, S):
		start = 0
		maxLen = 1
		size = len(S)
		for i in range(1, len(S)):
			l = i - 1
			r = i
			while l >= 0 and r < size and (S[l] == S[r]):
				if r - l + 1 > maxLen:
					maxLen = r - l + 1
					start = l
				l -= 1
				r += 1
			l = i - 1
			r = i + 1
			while l >= 0 and r < size and (S[l] == S[r]):
				if r - l + 1 > maxLen:
					maxLen = r - l + 1
					start = l
				l -= 1
				r += 1
		return S[start:start + maxLen]


class Solution:

	def longestPalindrome(self, S):
		s_len = len(S)
		for i in range(s_len, 0, -1):
			for j in range(0, s_len - i + 1):
				if self.is_palindrome(S[j:i + j]):
					return S[j:i + j]

	def is_palindrome(self, S):
		s_len = len(S)
		for i in range(0, s_len // 2 + 1):
			if S[i] != S[s_len - 1 - i]:
				return False
		return True

	def iis_palindrome(self, S):
		s_len = len(S)
		i = 0
		while i < s_len / 2:
			if S[i] != S[s_len - 1 - i]:
				return False
			i += 1
		return True


class Solution:

	def longestPalindrome(self, S):
		maxx = 1
		n = len(S)
		ans = S[0]
		for i in range(1, n):
			(j, k) = (-1, -1)
			subs = S[i]
			(st, m) = (True, i)
			res = 0
			for j in range(i - 1, -1, -1):
				if S[j] == S[i]:
					subs += S[i]
				else:
					break
			for k in range(i + 1, n):
				if S[k] == S[i]:
					subs += S[i]
				else:
					break
			if j == -1 or k == -1:
				continue
			(a, b) = (j, k)
			while a >= 0 and b < n:
				if S[a] == S[b]:
					subs = S[a] + subs + S[a]
					a -= 1
					b += 1
				else:
					break
			if len(subs) > len(ans):
				ans = subs
		return ans


class Solution:

	def longestPalindrome(self, S):
		if len(S) == 1:
			return S
		for i in range(len(S), 0, -1):
			for j in range(len(S) - i + 1):
				res = S[j:i + j]
				if res == res[::-1]:
					return res


class Solution:

	def longestPalindrome(self, S):
		total = ''
		n = len(S)
		for i in range(n):
			l = i
			r = i
			while l >= 0 and r < n and (S[l] == S[r]):
				if len(total) < r - l + 1:
					total = S[l:r + 1]
				l -= 1
				r += 1
		for i in range(n - 1):
			l = i
			r = i + 1
			while l >= 0 and r < n and (S[l] == S[r]):
				if len(total) < r - l + 1:
					total = S[l:r + 1]
				l -= 1
				r += 1
		return total


class Solution:

	def longestPalindrome(self, S):
		n = len(S)
		t = [[0 for i in range(len(S))] for j in range(len(S))]
		start = 0
		end = 0
		for i in range(n):
			t[i][i] = 1
		gmax = 1
		count = 0
		for i in range(1, n):
			if S[i - 1] == S[i]:
				t[i - 1][i] = 1
				gmax = max(gmax, 2)
				if count == 0:
					start = i - 1
					end = i
					count = 1
		for k in range(3, n + 1):
			count = 0
			for i in range(n - k + 1):
				j = k + i - 1
				if t[i + 1][j - 1] == 1 and S[i] == S[j]:
					t[i][j] = 1
					gmax = max(gmax, k)
					if count == 0:
						start = i
						end = j
						count = 1
		return S[start:end + 1]


class Solution:

	def longestPalindrome(self, s):
		ans = ''
		res = 0
		j = 0
		n = len(s)
		while j < n:
			left = j - 1
			right = j + 1
			while left >= 0 and right < n and (s[left] == s[right]):
				left -= 1
				right += 1
			l = j
			r = j + 1
			while l >= 0 and r < n and (s[l] == s[r]):
				r += 1
				l -= 1
			temp = right - left
			temp2 = r - l
			if temp < temp2:
				if res < temp2:
					res = temp2
					ans = s[l + 1:r]
			elif res < temp:
				res = temp
				ans = s[left + 1:right]
			j += 1
		if len(ans) == 1:
			return s[0]
		else:
			return ans


class Solution:

	def longestPalindrome(self, S):
		ans = ''
		anslen = 0
		for i in range(0, len(S)):
			l = i
			r = i
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				if r - l + 1 > anslen:
					ans = S[l:r + 1]
					anslen = r - l + 1
				l = l - 1
				r = r + 1
			l = i
			r = i + 1
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				if r - l + 1 > anslen:
					ans = S[l:r + 1]
					anslen = r - l + 1
				l = l - 1
				r = r + 1
		return ans


class Solution:

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


class Solution:

	def longestPalindrome(self, s):
		maxi = 0
		res = ''
		for i in range(len(s)):
			l = i
			r = i
			while (l >= 0 and r < len(s)) and s[l] == s[r]:
				if r - l + 1 > maxi:
					res = s[l:r + 1]
					maxi = r - l + 1
				l = l - 1
				r = r + 1
			a = i
			b = i + 1
			while (a >= 0 and b < len(s)) and s[a] == s[b]:
				if b - a + 1 > maxi:
					res = s[a:b + 1]
					maxi = b - a + 1
				a = a - 1
				b = b + 1
		return res


class Solution:

	def longestPalindrome(self, s):
		l = []
		m = 1
		for i in range(len(s)):
			a = []
			for j in range(len(s)):
				a.append(0)
			l.append(a)
		i = 0
		j = 0
		k = 1
		while j < len(s):
			while j < len(s):
				if s[i] == s[j]:
					if i == j:
						l[i][j] = 1
						if m < l[i][j]:
							m = l[i][j]
							(x, y) = (i, j)
					elif abs(i - j) == 1:
						l[i][j] = 2
						if m < l[i][j]:
							m = l[i][j]
							(x, y) = (i, j)
					elif l[i + 1][j - 1] > 0:
						l[i][j] = l[i + 1][j - 1] + 2
						if m < l[i][j]:
							m = l[i][j]
							(x, y) = (i, j)
					else:
						l[i][j] = 0
				else:
					l[i][j] = 0
				i = i + 1
				j = j + 1
			i = 0
			j = k
			k = k + 1
		if m > 1:
			return s[x:y + 1]
		else:
			return s[0]


class Solution:

	def longestPalindrome(self, S):
		for i in range(len(S), 0, -1):
			window_length = len(S) - i
			for j in range(window_length + 1):
				current_str = S[j:i + j]
				if current_str == current_str[::-1]:
					return current_str
		return s[0]


class Solution:

	def longestPalindrome(self, S):
		a1 = {}
		for i in range(len(S)):
			p1 = i
			p2 = i
			while p1 >= 0 and p2 < len(S) and (S[p1] == S[p2]):
				if p2 - p1 + 1 not in a1:
					a1[p2 - p1 + 1] = [p1, p2]
				elif a1[p2 - p1 + 1][0] > p1:
					a1[p2 - p1 + 1] = [p1, p2]
				p1 -= 1
				p2 += 1
			p1 = i
			p2 = i + 1
			while p1 >= 0 and p2 < len(S) and (S[p1] == S[p2]):
				if p2 - p1 + 1 not in a1:
					a1[p2 - p1 + 1] = [p1, p2]
				elif a1[p2 - p1 + 1][0] > p1:
					a1[p2 - p1 + 1] = [p1, p2]
				p1 -= 1
				p2 += 1
		return S[a1[max(a1)][0]:a1[max(a1)][1] + 1]


class Solution:

	def longestPalindrome(self, S):
		if len(S) <= 1:
			return S
		maxl = 1
		n = len(S)
		(st, en) = (0, 0)
		for i in range(n - 1):
			(l, r) = (i, i)
			while l >= 0 and r < n:
				if S[l] == S[r]:
					l -= 1
					r += 1
				else:
					break
			len1 = r - l - 1
			if len1 > maxl:
				maxl = len1
				(st, en) = (l + 1, r - 1)
		for i in range(n - 1):
			(l, r) = (i, i + 1)
			while l >= 0 and r < n:
				if S[l] == S[r]:
					l -= 1
					r += 1
				else:
					break
			len1 = r - l - 1
			if len1 > maxl:
				maxl = len1
				(st, en) = (l + 1, r - 1)
		return S[st:en + 1]


class Solution:

	def longestPalindrome(self, S):
		n = len(S)
		for i in range(n):
			for j in range(i + 1):
				s = S[j:j + n - i]
				if s == s[::-1]:
					return s


class Solution:

	def longestPalindrome(self, s):
		if len(s) == 1:
			return s
		f = 1

		def palindrom(sub):
			start = 0
			end = len(sub) - 1
			while start < end:
				if sub[start] != sub[end]:
					return False
				start += 1
				end -= 1
			return True
		length = 1
		for i in range(len(s)):
			for j in range(i + 1, len(s) + 1):
				if palindrom(s[i:j]) and (len(s[i:j]) > length or f):
					string = s[i:j]
					length = len(s[i:j])
					f = 0
		return string


class Solution:

	def longestPalindrome(self, S):
		n = len(S)
		maxi = 1
		ans = S[0]
		for i in range(n):
			for j in range(i + 1, n + 1):
				if S[i:j] == S[i:j][::-1]:
					if len(S[i:j]) > maxi:
						maxi = len(S[i:j])
						ans = S[i:j]
		return ans


class Solution:

	def longestPalindrome(self, S):
		a = []
		for i in range(len(S)):
			for j in range(i + 1, len(S) + 1):
				s = S[i:j]
				if s == s[::-1]:
					a.append(s)
		c = ''
		l = 0
		for i in a:
			if len(i) > l:
				l = len(i)
				c = i
		return c


class Solution:

	def longestPalindrome(self, S):
		n = len(S)
		start = 0
		max_len = 1
		for i in range(0, n):
			low = i - 1
			high = i + 1
			while high < n and S[high] == S[i]:
				high = high + 1
			while low >= 0 and S[low] == S[i]:
				low = low - 1
			while low >= 0 and high < n and (S[low] == S[high]):
				low = low - 1
				high = high + 1
			if max_len < high - low - 1:
				max_len = high - low - 1
				start = low + 1
		return S[start:start + max_len]


class Solution:

	def longestPalindrome(self, S):
		str1 = ''
		str2 = ''
		strlen = 0
		if len(S) == 1:
			return S
		for i in range(0, len(S)):
			l = i
			r = i + 1
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				if r - l + 1 > strlen:
					str1 = S[l:r + 1]
					strlen = r - l + 1
				l -= 1
				r += 1
		for i in range(0, len(S)):
			l = i
			r = i
			while l >= 0 and r < len(S) and (S[l] == S[r]):
				if r - l + 1 > strlen:
					str2 = S[l:r + 1]
					strlen = r - l + 1
				l -= 1
				r += 1
		if len(str1) > len(str2):
			return str1
		else:
			return str2


class Solution:

	def longestPalindrome(self, s):
		dp = []
		ans = ''
		maxi = 0
		for i in range(len(s)):
			dp.append([0] * len(s))
		for i in range(len(s)):
			dp[i][i] = 1
			if i == 0:
				ans = s[i]
		lent = 1
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				dp[i][i + 1] = 1
				if lent > maxi:
					ans = s[i:i + 2]
					maxi = lent
		for lent in range(2, len(s)):
			i = 0
			while i + lent < len(s):
				if s[i] == s[i + lent] and dp[i + 1][i + lent - 1] == 1:
					dp[i][i + lent] = 1
					if lent > maxi:
						ans = s[i:i + lent + 1]
						maxi = lent
				i += 1
		return ans


class Solution:

	def longestPalindrome(self, s):
		n = len(s)
		dp = [[0] * n for i in range(n)]
		maxlen = 1
		start = 0
		i = 0
		while i <= n - 1:
			dp[i][i] = True
			i += 1
		flag = False
		i = 0
		while i <= n - 2:
			if s[i] == s[i + 1]:
				dp[i][i + 1] = True
				if flag == False:
					start = i
					maxlen = 2
					flag = True
			i += 1
		k = 3
		for k in range(3, n + 1):
			for i in range(0, n - k + 1):
				j = i + k - 1
				if s[i] == s[j] and dp[i + 1][j - 1] == True:
					dp[i][j] = True
					if k > maxlen:
						maxlen = k
						start = i
		ans = s[start:start + maxlen]
		return ans


class Solution:

	def longestPalindrome(self, S):
		n = S
		res = n[0]
		m = 0
		dp = [[0] * len(n) for _ in range(len(n))]
		for i in range(len(n)):
			dp[i][i] = 1
		for i in range(len(n) - 1):
			if n[i] == n[i + 1]:
				dp[i][i + 1] = 1
				if len(res) < 2:
					res = n[i:i + 2]
		for j in range(2, len(n)):
			for i in range(len(n) - j):
				if n[i] == n[i + j] and dp[i + 1][i + j - 1] == 1:
					dp[i][i + j] = dp[i + 1][i + j - 1]
					if len(res) < j + 1:
						res = n[i:i + j + 1]
		return res


class Solution:

	def longestPalindrome(self, S):
		s = S
		n = len(s)
		res = ''
		rl = 0
		for i in range(n):
			(l, r) = (i, i)
			while l >= 0 and r < n and (s[l] == s[r]):
				if r - l + 1 > rl:
					res = s[l:r + 1]
					rl = r - l + 1
				l -= 1
				r += 1
			(l, r) = (i, i + 1)
			while l >= 0 and r < n and (s[l] == s[r]):
				if r - l + 1 > rl:
					res = s[l:r + 1]
					rl = r - l + 1
				l -= 1
				r += 1
		return res


class Solution:

	def longestPalindrome(self, s):
		m = 0
		for i in range(len(s)):
			for j in range(i, len(s) + 1):
				w = s[i:j]
				rev = w[::-1]
				if w == rev:
					if len(w) > m:
						m = len(w)
						W = w
		return W


class Solution:

	def expand(self, s, l, r):
		while l >= 0 and r < len(s) and (s[l] == s[r]):
			l -= 1
			r += 1
		return s[l + 1:r]

	def longestPalindrome(self, S):
		ans = ''
		for i in range(len(S)):
			tmp = self.expand(S, i, i)
			if len(tmp) > len(ans):
				ans = tmp
			tmp = self.expand(S, i, i + 1)
			if len(tmp) > len(ans):
				ans = tmp
		return ans


class Solution:

	def ispal(self, s):
		i = 0
		j = len(s) - 1
		while i <= j:
			if s[i] != s[j]:
				return 0
			i += 1
			j -= 1
		return 1

	def longestPalindrome(self, S):
		ans = ''
		mx = 0
		for i in range(len(S)):
			t = ''
			for j in range(i, len(S)):
				t += S[j]
				if self.ispal(t):
					if len(t) > mx:
						ans = t
						mx = len(t)
		return ans


class Solution:

	def longestPalindrome(self, S):

		def helper(i, j):
			while i >= 0 and j < len(S) and (S[i] == S[j]):
				i -= 1
				j += 1
			return S[i + 1:j]
		res = ''
		for i in range(len(S)):
			test = helper(i, i)
			if len(test) > len(res):
				res = test
			test = helper(i, i + 1)
			if len(test) > len(res):
				res = test
		return res


class Solution:

	def longestPalindrome(self, string):
		new_str = [None for i in range(2 * len(string) + 1)]
		j = 0
		for ch in string:
			new_str[j] = '#'
			new_str[j + 1] = ch
			j += 2
		new_str[j] = '#'
		lps = [0 for i in range(len(new_str))]
		(mx_lps_cntr, mx_lps_spread) = (0, 0)
		(i, r, c, mirr) = (0, 0, 0, 0)
		while i < len(new_str):
			mirr = 2 * c - i
			if i < r:
				lps[i] = min(lps[mirr], r - i)
			lt_chr = new_str[i - (lps[i] + 1)] if i - (lps[i] + 1) >= 0 else '$'
			rt_chr = new_str[i + (lps[i] + 1)] if i + (lps[i] + 1) < len(new_str) else '@'
			while lt_chr == rt_chr:
				lps[i] += 1
				lt_chr = new_str[i - (lps[i] + 1)] if i - (lps[i] + 1) >= 0 else '$'
				rt_chr = new_str[i + (lps[i] + 1)] if i + (lps[i] + 1) < len(new_str) else '@'
			if i + lps[i] > r:
				(c, r) = (i, i + lps[i])
			if lps[i] > mx_lps_spread:
				(mx_lps_cntr, mx_lps_spread) = (i, lps[i])
			i += 1
		return ''.join([new_str[i] for i in range(mx_lps_cntr - mx_lps_spread, mx_lps_cntr + mx_lps_spread + 1) if new_str[i] != '#'])


class Solution:

	def longestPalindrome(self, S):
		dp = []
		for i in range(len(S)):
			p = []
			for j in range(len(S)):
				p.append(0)
			dp.append(p)
		ans = 0
		for i in range(len(S)):
			j = 0
			k = i
			while k < len(S):
				if i == 0:
					dp[j][k] = 1
				elif i == 1 and S[j] == S[k]:
					dp[j][k] = 2
				elif S[j] == S[k] and dp[j + 1][k - 1]:
					dp[j][k] = dp[j + 1][k - 1] + 2
				if dp[j][k] > ans:
					ans = dp[j][k]
					string = S[j:k + 1]
				j = j + 1
				k = k + 1
		return string


class Solution:

	def __palin_expander__(self, i, j, string, n):
		while i >= 0 and j < n and (string[i] == string[j]):
			(i, j) = (i - 1, j + 1)
		return (i + 1, j - 1)

	def longestPalindrome(self, string):
		ans = [0, 0]
		for i in range(len(string)):
			(x, y) = self.__palin_expander__(i - 1, i + 1, string, len(string))
			if y - x + 1 > ans[1] - ans[0]:
				(ans[0], ans[1]) = (x, y + 1)
			(x, y) = self.__palin_expander__(i, i + 1, string, len(string))
			if y - x + 1 > ans[1] - ans[0]:
				(ans[0], ans[1]) = (x, y + 1)
		return string[ans[0]:ans[1]]


class Solution:

	def longestPalindrome(self, string):
		dp = [[True for j in range(len(string))] for i in range(2)]
		ans = [len(string) - 1, len(string)]
		for i in range(len(string) - 2, -1, -1):
			dp[0][i] = True
			if 1 > ans[1] - ans[0]:
				(ans[0], ans[1]) = (i, i + 1)
			if 1 == ans[1] - ans[0] and i < ans[0]:
				(ans[0], ans[1]) = (i, i + 1)
			for j in range(i + 1, len(string)):
				dp[0][j] = False
				if string[i] == string[j] and dp[1][j - 1]:
					dp[0][j] = True
					if j - i + 1 > ans[1] - ans[0]:
						(ans[0], ans[1]) = (i, j + 1)
					if j - i + 1 == ans[1] - ans[0] and i < ans[0]:
						(ans[0], ans[1]) = (i, j + 1)
			(dp[0], dp[1]) = (dp[1], dp[0])
		return string[ans[0]:ans[1]]


import sys
sys.setrecursionlimit(10000)

class Solution:

	def __count_palin_substr_helper(self, i, j, string):
		if i > j:
			return True
		if i == j:
			if 1 > self.ans[1] - self.ans[0]:
				(self.ans[0], self.ans[1]) = (i, j + 1)
			if 1 == self.ans[1] - self.ans[0] and i < self.ans[0]:
				(self.ans[0], self.ans[1]) = (i, j + 1)
			return True
		if self.dp[i][j] == None:
			self.dp[i][j] = False
			if string[i] == string[j] and self.__count_palin_substr_helper(i + 1, j - 1, string):
				self.dp[i][j] = True
				if j - i + 1 > self.ans[1] - self.ans[0]:
					(self.ans[0], self.ans[1]) = (i, j + 1)
				if j - i + 1 == self.ans[1] - self.ans[0] and i < self.ans[0]:
					(self.ans[0], self.ans[1]) = (i, j + 1)
			self.__count_palin_substr_helper(i, j - 1, string)
			self.__count_palin_substr_helper(i + 1, j, string)
		return self.dp[i][j]

	def longestPalindrome(self, string):
		self.dp = [[None for j in range(len(string))] for i in range(len(string))]
		self.ans = [0, 0]
		self.__count_palin_substr_helper(0, len(string) - 1, string)
		return string[self.ans[0]:self.ans[1]]


class Solution:

	def longestPalindrome(self, string):

		def is_palindrome(s):
			return s == s[::-1]
		longest_palindrome = ''
		for i in range(len(string)):
			for j in range(i + 1, len(string) + 1):
				substr = string[i:j]
				if is_palindrome(substr) and len(substr) > len(longest_palindrome):
					longest_palindrome = substr
		if longest_palindrome == '':
			return 'none'
		else:
			return longest_palindrome


class Solution:

	def longestPalindrome(self, S):

		def check_palindrome(st):
			is_palindrome = True
			n = len(st)
			for i in range(len(st) // 2):
				if st[i] != st[n - 1 - i]:
					is_palindrome = False
					break
			return is_palindrome
		st_input = S
		max_palindrome_len = 1
		max_palindrome = st_input[0]
		for i in range(len(st_input)):
			for j in range(i + 1, len(st_input) + 1):
				is_palindrome = check_palindrome(st_input[i:j])
				if is_palindrome and j - i > max_palindrome_len:
					max_palindrome = st_input[i:j]
					max_palindrome_len = j - i
		return max_palindrome


class Solution:

	def longestPalindrome(self, S):
		ans = S[0]
		dp = [[False for i in range(len(S))] for j in range(len(S))]
		for k in range(len(S)):
			i = 0
			j = k
			while j < len(S):
				if k == 0:
					dp[i][j] = True
				elif k == 1:
					if S[i] == S[j]:
						dp[i][j] = True
						if len(S[i:j + 1]) > len(ans):
							ans = S[i:j + 1]
					else:
						dp[i][j] = False
				elif S[i] == S[j] and dp[i + 1][j - 1] is True:
					dp[i][j] = True
					if len(S[i:j + 1]) > len(ans):
						ans = S[i:j + 1]
				else:
					dp[i][j] = False
				i += 1
				j += 1
		return ans


class Solution:

	def longestPalindrome(self, S):
		ans = ''
		for i in range(len(S)):
			for j in range(i + 1, len(S) + 1):
				string = S[i:j]
				if string == string[::-1] and len(string) > len(ans):
					ans = string
		return ans


class Solution:

	def longestPalindrome(self, s):
		a = 0
		st = ''
		for i in range(len(s)):
			for j in range(i + len(st), len(s)):
				if s[i:j + 1] == s[i:j + 1][::-1] and len(st) < len(s[i:j + 1]):
					st = s[i:j + 1]
		return st