Leetcode problem 5 solution using Python - Longest Palindromic Substring

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000

s consist of only digits and English letters.

Solution 1

This solution is not the best solution for this problem. But, it works for the leetcode and easy to understand. 

This solution utilizes the concept of expanding around the center. It iterates through each character in the string and treats it as the center of a potential palindrome. By expanding to the left and right, it checks if the characters are the same and increments the length of the palindrome. It keeps track of the maximum length and the starting position of the longest palindromic substring found so far.

You can watch this YouTube to understand the algorithm - https://youtu.be/XYQecbcd6_c 

class Solution:
  def longestPalindrome(self, s: str) -> str:
    res = ""
    lenRes = 0
    
    for i in range(len(s)):
      # odd number palindrome
      l, r = i, i 
      while l>=0 and r<len(s) and s[l]==s[r]:
        if (r-l+1)>lenRes:
          res = s[l:r+1]
          lenRes = r-l+1
        l = l -1
        r = r + 1
      # even number palindrome
      l, r = i, i+1 
      while l>=0 and r<len(s) and s[l]==s[r]:
        if (r-l+1)>lenRes:
          res = s[l:r+1]
          lenRes = r-l+1
        l = l -1
        r = r + 1
    return(res)

Solution 2

This solution is based on Manacher's Algorithm. It is the most optimized solution for this problem. It works by transforming the original string to include special characters (in this case, '#') between each character and at the beginning and end. This transformation allows us to handle both even and odd-length palindromes in a single loop. 

This algorithm is hard to understand. You can watch this video to understand it - https://youtu.be/IvakBbsAhUU  

class Solution:
  def longestPalindrome(self, s: str) -> str:
    # @ and $ signs are sentinels appended to each end to avoid bounds checking
    t = '#'.join('@' + s + '$')
    n = len(t)
    # t[i - maxExtends[i]..i) ==
    # t[i + 1..i + maxExtends[i]]
    maxExtends = [0] * n
    center = 0
    for i in range(1, n - 1):
      rightBoundary = center + maxExtends[center]
      mirrorIndex = center - (i - center)
      maxExtends[i] = rightBoundary > i and \
          min(rightBoundary - i, maxExtends[mirrorIndex])
      # Attempt to expand palindrome centered at i
      while t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]]:
        maxExtends[i] += 1
      # If palindrome centered at i expand past rightBoundary,
      # adjust center based on expanded palindrome.
      if i + maxExtends[i] > rightBoundary:
        center = i
    # Find the maxExtend and bestCenter
    maxExtend, bestCenter = max((extend, i) for i, extend in enumerate(maxExtends))
    return s[(bestCenter - maxExtend) // 2:(bestCenter + maxExtend) // 2]