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 that reads the same backward. More formally, S is a palindrome if reverse(S) = S. In case of conflict, return the substring which occurs first ( with the least starting index).
Example 1:
Input:
S = "aaaabbaa"
Output: aabbaa
Explanation: The longest Palindromic
substring is "aabbaa".
Example 2:
Input: 
S = "abc"
Output: a
Explanation: "a", "b" and "c" are the 
longest palindromes with same length.
The result is the one with the least
starting index.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestPalin() which takes the string S as input and returns the longest palindromic substring of S.
Expected Time Complexity: O(|S|^{2}).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def longestPalin(self, S):
        # code here

Solutions:
class Solution:

	def longestPalin(self, s):
		n = len(s)
		r = s[::-1]
		if r == s:
			return s
		elif n == 1:
			return s
		for i in range(n, 0, -1):
			for j in range(n - i + 1):
				h = s[j:i + j]
				if h == h[::-1]:
					return h


class Solution:

	def chekPalindrom(self, s, n, l, r):
		while r < n and l >= 0:
			if s[l] != s[r]:
				break
			l -= 1
			r += 1
		return (l + 1, r)

	def longestPalin(self, S):
		(st, en, n) = (0, 0, len(S))
		for i in range(n):
			(l, r) = self.chekPalindrom(S, n, i, i)
			if r - l > en - st:
				st = l
				en = r
			(l, r) = self.chekPalindrom(S, n, i, i + 1)
			if r - l > en - st:
				st = l
				en = r
		return S[st:en]


class Solution:

	def lp(self, s, l, r):
		n = len(s)
		while r < n and l >= 0:
			if s[l] != s[r]:
				break
			l -= 1
			r += 1
		return (l + 1, r)

	def longestPalin(self, S):
		s = S
		n = len(s)
		(start, end) = (0, 0)
		for i in range(n):
			(l, r) = self.lp(S, i, i)
			if r - l > end - start:
				end = r
				start = l
			(l, r) = self.lp(S, i, i + 1)
			if r - l > end - start:
				end = r
				start = l
		return s[start:end]


class Solution:

	def longestPalin(self, s):

		def fun(s, l, r):
			n = len(s)
			while l >= 0 and r < n and (s[l] == s[r]):
				l -= 1
				r += 1
			return (l + 1, r)
		start = end = 0
		for i in range(len(s)):
			(b1, b2) = fun(s, i, i)
			if b2 - b1 > end - start:
				start = b1
				end = b2
			(b1, b2) = fun(s, i, i + 1)
			if b2 - b1 > end - start:
				start = b1
				end = b2
		return s[start:end]


class Solution:

	def longestPalin(self, S):
		n = len(S)
		longest_palindrome = ''
		for i in range(n):
			left = i
			right = i
			while left >= 0 and right < n and (S[left] == S[right]):
				left -= 1
				right += 1
			if right - left - 1 > len(longest_palindrome):
				longest_palindrome = S[left + 1:right]
			left = i
			right = i + 1
			while left >= 0 and right < n and (S[left] == S[right]):
				left -= 1
				right += 1
			if right - left - 1 > len(longest_palindrome):
				longest_palindrome = S[left + 1:right]
		return longest_palindrome


class Solution:

	def longestPalin(self, s):
		if len(s) < 2:
			return s
		processed = '#' + '#'.join(s) + '#'
		center = 0
		max_right = 0
		max_len = 0
		start = 0
		palindrome_lengths = [0] * len(processed)
		for i in range(len(processed)):
			if i < max_right:
				mirror = 2 * center - i
				palindrome_lengths[i] = min(max_right - i, palindrome_lengths[mirror])
			left = i - (palindrome_lengths[i] + 1)
			right = i + (palindrome_lengths[i] + 1)
			while left >= 0 and right < len(processed) and (processed[left] == processed[right]):
				palindrome_lengths[i] += 1
				left -= 1
				right += 1
			if i + palindrome_lengths[i] > max_right:
				center = i
				max_right = i + palindrome_lengths[i]
			if palindrome_lengths[i] > max_len:
				max_len = palindrome_lengths[i]
				start = (i - max_len) // 2
		return s[start:start + max_len]


class Solution:

	def longestPalin(self, s):
		a = 1
		b = s[0]
		n = len(s)
		for i in range(n):
			for j in range(i + a + 1, n + 1):
				sub = s[i:j]
				if sub == sub[::-1]:
					a = len(sub)
					b = sub
		return b


class Solution:

	def longestPalin(self, S):

		def isPalindrome(s, i, j):
			n = len(s)
			while i >= 0 and j < n and (s[i] == s[j]):
				i -= 1
				j += 1
			return s[i + 1:j]
		n = len(S)
		mx = ''
		for i in range(n):
			res = isPalindrome(S, i, i)
			mx = max(mx, res, key=len)
			res = isPalindrome(S, i, i + 1)
			mx = max(mx, res, key=len)
		return mx


class Solution:

	def longestPalin(self, s: str) -> str:
		if s == s[::-1]:
			return s
		(start, size) = (0, 1)
		for i in range(1, len(s)):
			(l, r) = (i - size, i + 1)
			(s1, s2) = (s[l - 1:r], s[l:r])
			if l >= 1 and s1 == s1[::-1]:
				size += 2
				start = l - 1
			elif s2 == s2[::-1]:
				size += 1
				start = l
		return s[start:start + size]


class Solution:

	def longestPalin(self, s):
		if len(s) == 1:
			return s
		for i in range(len(s), 0, -1):
			for j in range(len(s) - i + 1):
				x = s[j:i + j]
				if x == x[::-1]:
					return x


class Solution:

	def longestPalin(self, S):
		fi = fj = 0
		n = len(S)
		for i in range(n):
			j = i - 1
			k = i + 1
			while j >= 0 and k < n:
				if S[j] != S[k]:
					break
				j -= 1
				k += 1
			if k - j - 1 > fj - fi + 1:
				fi = j + 1
				fj = k - 1
			if i < n - 1 and S[i] == S[i + 1]:
				j = i - 1
				k = i + 2
				while j >= 0 and k < n:
					if S[j] != S[k]:
						break
					j -= 1
					k += 1
				if k - j - 1 > fj - fi + 1:
					fi = j + 1
					fj = k - 1
		return S[fi:fj + 1]


class Solution:

	def longestPalin(self, S):
		if S == S[::-1]:
			return S
		count = 0
		out = ''
		for i in range(len(S)):
			for j in range(i + 1, len(S) + 1):
				p = S[i:j]
				if p == p[::-1]:
					if len(S[i:j]) > count:
						count = len(S[i:j])
						out = S[i:j]
		return out


class Solution:

	def longestPalin(self, s):
		ans = ''
		n = len(s)
		le = 0
		for i in range(n):
			for j in range(i, n):
				if s[i] == s[j] and i != j and (j - i + 1 > le):
					s1 = ''
					s2 = ''
					s3 = ''
					if (j - i) % 2 == 0:
						s1 = s[i:(j + i) // 2]
						s3 = s[(j + i) // 2]
						s2 = s[(j + i) // 2 + 1:j + 1]
					else:
						s1 = s[i:(j + i) // 2 + 1]
						s2 = s[(j + i) // 2 + 1:j + 1]
					if s1 == s2[::-1]:
						ans = s1 + s3 + s2
						le = len(ans)
		if ans == '':
			return s[0]
		return ans


class Solution:

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


class Solution:

	def longestPalin(self, S):
		n = len(S)
		max_len = 1
		start_idx = 0
		for i in range(n):
			j = i
			k = i
			while j >= 0 and k < n and (S[j] == S[k]):
				if k - j + 1 > max_len:
					max_len = k - j + 1
					start_idx = j
				j -= 1
				k += 1
			if max_len >= 2 * (n - i) - 1:
				break
		for i in range(n - 1):
			j = i
			k = i + 1
			while j >= 0 and k < n and (S[j] == S[k]):
				if k - j + 1 > max_len:
					max_len = k - j + 1
					start_idx = j
				j -= 1
				k += 1
			if max_len >= 2 * (n - i) - 1:
				break
		return S[start_idx:start_idx + max_len]


class Solution:

	def longestPalin(self, S):

		def check(s, start, end):
			while start < end:
				if s[start] != s[end]:
					return False
				start += 1
				end -= 1
			return True
		maxLen = 1
		start = 0
		for i in range(len(S)):
			for j in range(i + 1, len(S)):
				if j - i + 1 > maxLen and check(S, i, j):
					start = i
					maxLen = j - i + 1
		return S[start:start + maxLen]


class Solution:

	def longestPalin(self, S):
		res = ''
		s2 = 0
		if S == S[::-1]:
			return S
		for i in range(len(S)):
			st = ''
			s1 = 0
			for j in range(i, len(S)):
				st += S[j]
				s1 += 1
				if st == st[::-1]:
					if s1 > s2:
						res = st
						s2 = s1
		return res


class Solution:

	def longestPalin(self, S):
		maxlen = 1
		n = len(S)
		leng = 0
		start = 0
		end = 0
		if len(S) <= 1:
			return S
		for i in range(0, n):
			l = i
			r = i
			while l >= 0 and r < n:
				if S[l] == S[r]:
					l -= 1
					r += 1
				else:
					break
			leng = r - l - 1
			if leng > maxlen:
				maxlen = leng
				start = l + 1
				end = r
			l = i
			r = i + 1
			while l >= 0 and r < n:
				if S[l] == S[r]:
					l -= 1
					r += 1
				else:
					break
			leng = r - l - 1
			if leng > maxlen:
				maxlen = leng
				start = l + 1
				end = r
		if start == 0 and end == 0:
			return S[0]
		return S[start:end]


class Solution:

	def longestPalin(self, S):
		max = 1
		ans = S[0]
		for i in range(len(S)):
			for j in range(i + max + 1, len(S) + 1):
				str = S[i:j]
				if str == str[::-1]:
					max = len(str)
					ans = str
		return ans


class Solution:

	def longestPalin(self, S):
		rev = S[::-1]
		i = 0
		j = 1
		s2 = ''
		a = len(S)
		s3 = ''
		while i < a and j < a + 1:
			if S[i:j] not in rev:
				i = i + 1
				j = i + len(s2) + 1
			else:
				s3 = S[i:j]
				j = j + 1
			if s3 == s3[::-1]:
				s2 = s3
		return s2


class Solution:

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


class Solution:

	def isPlaindrome(self, s, low, high):
		while low <= high:
			if s[low] != s[high]:
				return False
			low += 1
			high -= 1
		return True

	def longestPalin(self, S):
		if S == S[::-1]:
			return S
		max_p = ''
		n = len(S)
		for i in range(n):
			for j in range(i, n):
				if self.isPlaindrome(S, i, j) and len(max_p) < j - i + 1:
					max_p = S[i:j + 1]
			if len(max_p) > n - i:
				break
		return max_p


class Solution:

	def is_palindrome(self, data):
		(i, j) = (0, len(data) - 1)
		while i < j:
			if data[i] != data[j]:
				return False
			i += 1
			j -= 1
		return True

	def longestPalin(self, S):
		n = len(S)
		ans = S[0]
		i = 0
		while n - i >= len(ans):
			temp = S[i]
			for j in range(i + 1, n):
				temp += S[j]
				if len(temp) > len(ans) and self.is_palindrome(temp):
					ans = temp
			i += 1
		return ans


class Solution:

	def longestPalin(self, S):
		if S == S[::-1]:
			return S
		max_p = ''
		n = len(S)
		for i in range(n):
			s1 = ''
			for j in range(i, n):
				s1 += S[j]
				if s1 == s1[::-1] and len(max_p) < len(s1):
					max_p = s1
			if len(max_p) > n - i:
				break
		return max_p


class Solution:

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


class Solution:

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


class Solution:

	def ispalindrome(self, i, j, s):
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True

	def longestPalin(self, S):
		n = len(S)
		max1 = 0
		ind = 0
		for i in range(n):
			for j in range(i, n):
				if j - i + 1 > max1 and self.ispalindrome(i, j, S):
					max1 = j - i + 1
					ind = i
		return S[ind:max1 + ind]


class Solution:

	def longestPalin(self, S):
		n = len(S)
		if n <= 1:
			return S
		max_len = 1
		(st, e) = (0, 0)
		for i in range(n - 1):
			(l, r) = (i, i)
			while l >= 0 and r < n:
				if S[l] == S[r]:
					(l, r) = (l - 1, r + 1)
				else:
					break
			length = r - l - 1
			if length > max_len:
				max_len = length
				(st, e) = (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
			length = r - l - 1
			if length > max_len:
				max_len = length
				(st, e) = (l + 1, r - 1)
		return S[st:e + 1]


class Solution:

	def longestPalin(self, s):
		n = len(s)
		if n <= 1:
			return s
		max_ = 0
		start = 0
		end = 0
		for i in range(n - 1):
			l = i
			r = i
			while l >= 0 and r < n:
				if s[l] == s[r]:
					l -= 1
					r += 1
				else:
					break
			len_ = r - l - 1
			if len_ > max_:
				max_ = len_
				start = l + 1
				end = r - 1
		for i in range(n - 1):
			l = i
			r = i + 1
			while l >= 0 and r < n:
				if s[l] == s[r]:
					l -= 1
					r += 1
				else:
					break
			len_ = r - l - 1
			if len_ > max_:
				max_ = len_
				start = l + 1
				end = r - 1
		return s[start:end + 1]


class Solution:

	def longestPalin(self, s: str) -> str:
		n = len(s)
		if n < 2:
			return s
		(start, end, max_len) = (0, 0, 1)
		for i in range(n):
			len1 = self.expand_around_center(s, i, i)
			len2 = self.expand_around_center(s, i, i + 1)
			cur_len = max(len1, len2)
			if cur_len > max_len:
				max_len = cur_len
				start = i - (cur_len - 1) // 2
				end = i + cur_len // 2
		return s[start:end + 1]

	def expand_around_center(self, s: str, left: int, right: int) -> int:
		n = len(s)
		while left >= 0 and right < n and (s[left] == s[right]):
			left -= 1
			right += 1
		return right - left - 1


class Solution:

	def longestPalin(self, S):
		ans = ''

		def palin(s):
			i = 0
			j = len(s) - 1
			while i <= j:
				if s[i] != s[j]:
					return False
				i += 1
				j -= 1
			return True
		for i in range(len(S)):
			if len(S) - i < len(ans):
				break
			for j in range(i + 1, len(S)):
				if S[i] == S[j]:
					s1 = S[i:j + 1]
					if palin(s1) and len(s1) > len(ans):
						ans = s1
		if ans == '':
			return S[0]
		return ans


class Solution:

	def longestPalin(self, S):
		i = 0
		n = len(S)
		j = n - 1
		Srev = ''
		Slist = []
		while i < n:
			j = n - 1
			while j >= 0:
				if S[i] == S[j]:
					Srev = ''.join(reversed(S[i:j + 1]))
					if S[i:j + 1] == Srev:
						Slist.append(S[i:j + 1])
						break
				j -= 1
			i += 1
		res = max(Slist, key=len)
		return res


class Solution:

	def longestPalin(self, s):
		n = len(s)
		start = 0
		max_len = 1

		def expand(left, right):
			while left >= 0 and right < n and (s[left] == s[right]):
				left -= 1
				right += 1
			return right - left - 1
		for i in range(n):
			len1 = expand(i, i)
			len2 = expand(i, i + 1)
			cm_len = max(len1, len2)
			if cm_len > max_len:
				max_len = cm_len
				start = i - (cm_len - 1) // 2
		return s[start:start + max_len]


class Solution:

	def longestPalin(self, S):
		best_begin_idx = best_end_idx = begin_idx = 0
		while begin_idx < len(S):
			begin_pointer = begin_idx
			end_idx = end_pointer = len(S) - 1
			is_palindrome = True
			while end_pointer >= begin_pointer:
				if S[begin_pointer] == S[end_pointer]:
					begin_pointer += 1
					end_pointer -= 1
					is_palindrome = True
				else:
					end_idx -= 1
					end_pointer = end_idx
					begin_pointer = begin_idx
					is_palindrome = False
			if is_palindrome:
				if end_idx - begin_idx > best_end_idx - best_begin_idx:
					best_begin_idx = begin_idx
					best_end_idx = end_idx
			begin_idx += 1
		return S[best_begin_idx:best_end_idx + 1]


class Solution:

	def longestPalin(self, S):
		ln = len(S)

		def cp(l, r):
			while l >= 0 and r < ln and (S[l] == S[r]):
				l -= 1
				r += 1
			return r - l - 1
		e = 0
		s = 0
		for i in range(ln):
			odd = cp(i, i)
			even = cp(i, i + 1)
			spl = max(even, odd)
			if spl > e:
				e = spl
				s = i - (spl - 1) // 2
		return S[s:s + e]


class Solution:

	def longestPalin(self, S):
		ans = ''
		n = len(S)
		for i in range(n):
			if len(S[i:]) < len(ans):
				return ans
			for j in range(n, i, -1):
				k = S[i:j]
				rev = k[::-1]
				if k == rev and len(k) > len(ans):
					ans = k
		return ans


class Solution:

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

	def longestPalin(self, s):
		result = ''
		reslen = 0
		if len(s) == 1:
			return s[0]
		for i in range(len(s)):
			(l, r) = self.lp(s, i, i)
			if r - l > reslen:
				reslen = r - l
				result = s[l:r]
			(l, r) = self.lp(s, i, i + 1)
			if r - l > reslen:
				reslen = r - l
				result = s[l:r]
		return result


class Solution:

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


class Solution:

	def longestPalin(self, S2):
		n = len(S)
		ans = ''
		for i in range(n):
			temp = expandAroundCenter(S, i, i)
			if len(temp) > len(ans):
				ans = temp
			temp = expandAroundCenter(S, i, i + 1)
			if len(temp) > len(ans):
				ans = temp
		return ans

def expandAroundCenter(s, left, right):
	while left >= 0 and right < len(s) and (s[left] == s[right]):
		left -= 1
		right += 1
	return s[left + 1:right]


class Solution:

	def longestPalin(self, str):
		a = ''
		s = 0
		if str == str[::-1]:
			return str
		for i in range(len(str)):
			b = ''
			s1 = 0
			for j in range(i, len(str)):
				b += str[j]
				s1 += 1
				if b == b[::-1]:
					if s1 > s:
						a = b
						s = s1
		return a