5. Longest Palindromic Substring

🟨 Medium

Question

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

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

Approach: Expand Around Center

• Time complexity: O(n^2)

• Space complexity: O(1)

def longestPalindrome(self, s: str) -> str:
    n = len(s)
    if n < 2: #single char is a palindrome
        return s
    res = "" #init result string
    for i in range(len(s)):
        l1 = self.checkPalindrome(s, i, i) #for "aba" pattern
        l2 = self.checkPalindrome(s, i, i+1) #for "abba" pattern
        longer = l1 if len(l1) > len(l2) else l2; 
        #change result if find longer palindromic substring
        res = longer if len(longer) > len(res) else res 
    return res
    
def checkPalindrome(self, s, l, r): #helper function
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l+1:r]

Manacher's Algorithm

• Time complexity: O(n)

• Space complexity: O(1)

Explanation | YouTube