class Solution:
    def longestPalindrome(self, s: str) -> str:
        '''
        Time Complexity: O(n^2)
        Space Complexity: O(1)
        Where, n is the length of the given string.
        
        NOTE: This is not the most optimal solution, we used Two pointers approach which is good enough for interview purposes.
        Can also be done with Dynamic Programming with O(n^2) time and space complexity.
        Most optimal solution is Manacher's Algorithm with time complexity of O(n) and space complexity of O(n).
        Refer https://neetcode.io/problems/longest-palindromic-substring/solution for most optimal solution.
        '''
        left, right = 0, 0
        maxLeft, maxRight = 0, 0

        def updateMax():
            nonlocal left, right, maxLeft, maxRight
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left-=1
                right+=1
            left+=1
            right-=1
            if right-left > maxRight-maxLeft:
                maxLeft = left
                maxRight = right

        for i in range(len(s)-1):
            left = i
            right = i
            updateMax()    
            left = i
            right = i+1
            updateMax()
        
        return s[maxLeft:maxRight+1]