Solutions

# Two pointers, brute force or 2d dp - O(n^2) time optimal
# dp

# Two pointers - O(n^2) time, O(1) space
def longestPalindrome(s: str) -> str:
    res = ""
    for i in range(len(s)):
        odd = get_max_palindrome(s, i, i)
        even = get_max_palindrome(s, i, i+1)
        res = max(odd, even, res, key=len)
    return res

def get_max_palindrome(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]

# Brute force - O(n^3) time, O(1) space
def longestPalindrome(s: str) -> str:
    res, resLen = "", 0

    for i in range(len(s)):
        for j in range(i, len(s)):
            l, r = i, j
            while l < r and s[l] == s[r]:
                l += 1
                r -= 1

            if l >= r and resLen < (j - i + 1):
                res = s[i : j + 1]
                resLen = j - i + 1
    return res

# 2d DP - O(n^2) time, O(n^2) space
def longestPalindrome(s: str) -> str:
    dp = [[False]*len(s) for _ in range(len(s))]

    resIdx, resLen = 0, 0
    for i in range(len(s) - 1, -1, -1):  # outer loop goes backwards to ensure dp[i+1][] is already calculated
        for j in range(i, len(s)):       # inner loop goes forward to ensure dp[][j-1] is already calculated
            if s[i] == s[j] and (j-i<=2 or dp[i+1][j-1]): # special case for length 1 and 2, otherwise check if the inner substring is palindrome
                dp[i][j] = True
                if j - i + 1 > resLen:
                    resIdx = i
                    resLen = j - i + 1
    return s[resIdx : resIdx+resLen]