5. Longest Palindromic Substring

Обновлено: 2024-03-12
3 мин
[String Dynamic Programming LeetCode Top Interview]

LeetCode problem

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

A string is called a palindrome string if the reverse of that string is the same as the original string.

Example 1:

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

Example 2:

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

First accepted

Hints

How can we reuse a previously computed palindrome to compute a larger palindrome?

How can we reuse a previously computed palindrome to compute a larger palindrome?

Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

Idea:

We start at index = 0 and iterate through all values until n. At each index we call the function getPalindrome that will check the values to the left and right of the provided indices. It will continue to do so until the longest palindrome within the given range is found.

test-case

LeetCode diagram explained

Link to diagram

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def getPalindrome(left, right):
            while(left >= 0 and
                  right < len(s) and
                  s[left] == s[right]):
                left -= 1
                right += 1
                
            return left+1, right-1
            
        pal_left = 0
        pal_right = 0
        len_max = 1
        
        for i in range(len(s)):
            left, right = getPalindrome(i, i)
            pal_len= right - left + 1
            if pal_len > len_max:
                pal_left = left
                pal_right = right
                len_max = pal_len
            
            left, right = getPalindrome(i, i+1)
            pal_len = right - left + 1
            if pal_len > len_max:
                pal_left = left
                pal_right = right
                len_max = pal_len
                
        return s[pal_left:pal_right+1]

Better solution

Manacher’s algorithm

There is an O(n) algorithm called Manacher’s algorithm.

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]

Resources

RU