<jupyter_start><jupyter_text>Longest Palindromic Substring[link](https://www.algoexpert.io/questions/Longest%20Palindromic%20Substring)  My Solution<jupyter_code># O(n^2) time | O(n) space
def longestPalindromicSubstring(string):
    # Write your code here.
    res = [0, 1]
    for centerIdx in range(1, len(string)):
        odd = findLongestPalindrome(string, centerIdx - 1, centerIdx + 1)
        even = findLongestPalindrome(string, centerIdx - 1, centerIdx)
        res = max(odd, even, res, key=lambda x: x[1] - x[0])
    return string[res[0]:res[1]]
            
def findLongestPalindrome(string, left, right):
    while left >= 0 and right < len(string):
        if string[left] != string[right]:
            break
        left -= 1
        right += 1
    return [left + 1, right]
# Manacher's Algorithm
# O(n) time | O(n) space
def longestPalindromicSubstring(string):
    # Write your code here.
    newString = "#" + "#".join(string) + "#"
    radiuses = [0 for x in newString] # not include the center
    longestCenter = 0
    left = 0
    right = 0
    for i in range(1, len(newString)):
        if i <= right:
            j = left + right - i
            radiuses[i] = min(j - left, radiuses[j])
        
        k = radiuses[i]
        while i - k - 1 >= 0 and i + k + 1 < len(newString):
            if newString[i - k - 1] == newString[i + k + 1]:
                k += 1
            else:
                break
        radiuses[i] = k
        potentialRight = i + k
        if potentialRight > right:
            right = potentialRight
            left = i - k
        if radiuses[i] > radiuses[longestCenter]:
            longestCenter = i
    resLeft = (longestCenter - radiuses[longestCenter]) // 2
    resRight = (longestCenter + radiuses[longestCenter] - 1) // 2 + 1
    return string[resLeft:resRight]
longestPalindromicSubstring('ababababababa')<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code># O(n^3) time | O(n) space
def longestPalindromicSubstring(string):
    longest = ""
	for i in range(len(string)):
		for j in range(i, len(string)):
			substring = string[i : j + 1]
			if len(substring) > len(longest) and isPalindrome(substring):
				longest = substring
	return longest

def isPalindrome(string):
	leftIdx = 0
	rightIdx = len(string) - 1
	while leftIdx < rightIdx:
		if string[leftIdx] != string[rightIdx]:
			return False
		leftIdx += 1
		rightIdx -= 1
	return True
# O(n^2) time | O(n) space
def longestPalindromicSubstring(string):
    currentLongest = [0, 1]
    for i in range(1, len(string)):
        odd = getLongestPalindromeFrom(string, i - 1, i + 1)
        even = getLongestPalindromeFrom(string, i - 1, i)
        longest = max(odd, even, key=lambda x: x[1] - x[0])
        currentLongest = max(longest, currentLongest, key=lambda x: x[1] - x[0])
    return string[currentLongest[0] : currentLongest[1]]

def getLongestPalindromeFrom(string, leftIdx, rightIdx):
    while leftIdx >= 0 and rightIdx < len(string):
        if string[leftIdx] != rightIdx[rightIdx]:
            break
        leftIdx += 1
        rightIdx -= 1
    return [leftIdx + 1, rightIdx]<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup