Question

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution

Expand from center. There are \(2n-1\) centers (each character and between two characters) that the palindrome can be positioned. Check the immediate left and right character are the same, and expand from there. It gives \(O(n^2)\) time complexity and constant space complexity.

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1:
            return s

        len_s = len(s)
        pali = ""
        length = 0

        for pos in range(0, 2 * len_s):
            if pos % 2 == 0:
                left, right = pos // 2, pos // 2
            else:
                left, right = pos // 2 + 1, pos // 2

            i = 0
            while left - i - 1 >= 0 and right + i + 1 < len_s and s[left-i-1] == s[right+i+1]:
                i += 1

            right = right + i
            left = left - i
            if left <= right and right - left + 1 > length:
                pali = s[left:right+1]
                length = right - left + 1

        return pali