5. Longest Palindromic Substring

link

Backtrack

Complexity O(n^3)

left and right n n, scan n

However, it will TLE

class Solution:
    def longestPalindrome(self, s: str) -> str:

        self.res = ''

        @cache
        def backtrack(s):
            if s == '':
                return
            if len(s) <= len(self.res):
                return
            l , r = 0 , len(s) - 1
            while l < r:
                if s[l] == s[r]:
                    l += 1
                    r -= 1
                else:
                    break

            if l >= r:
                self.res = s
                return
            
            ## because of this
            backtrack(s[1:])
            backtrack(s[:-1])

        backtrack(s)


        return self.res

can use two pointer and time complexity = O(n^2)

class Solution:
    def longestPalindrome(self, s: str) -> str:

        n = len(s)
        if n == 1:
            return s


        def check(i, j):

            while i >= 0 and j < n and s[i] == s[j]:
                i -= 1
                j += 1

            return s[i+1:j]

        res = ''

        for i in range(1, n):
            r1 = check(i, i)
    
            if r1 and len(r1) > len(res):
                res = r1

            r2 = check(i-1, i)

            if r2 and len(r2) > len(res):
                res = r2

        return res