https://leetcode.com/problems/longest-palindromic-substring

Let us look at possible places of middle of our palindrome and expand to the left and to the right until we either reached on of the ends of symbols are not equal. Also, because we need to return not only length of longest palindromic substring, but substring itself, our helper function will return this string.

Note also, that there are two different type of palindromes:

  1. With odd length, we use helper(k, k) for them.
  2. With even length, we use helper(k, k+1) for them.

Complexity There will be 2n - 1 possible centers and O(n) comparison for each of them, so final time complexity is O(n^2). Space complexity is O(n)

Further discussion there is also classical dynamic programming for this problem with also O(n^2) complexity, however in practice it can work much slower if we do not do optimiaztions: reason that it will be indeed n^2 operations, whereas on our approach here we do a lot of early stoppings. There is also ofcourse Manacher’s algorithm with complexity O(n), which sometimes useful for competitions, and you should have code avaliable somewhere, but which is in my opitions out of scope for middle difficulty problem.

class Solution:
    def longestPalindrome(self, s):
        n, ans = len(s), ""
        def helper(i, j):
            while i >= 0 and j < n and s[i] == s[j]:
                i, j = i - 1, j + 1
            return s[i + 1:j]
        
        for k in range(n):
            ans = max(helper(k, k), helper(k, k + 1), ans, key=len)
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 0005