5. Longest Palindromic Substring
Содержание
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.
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
- Manacher’s algorithm
- Errichto:LeetCode problem Longest Palindromic Substring (two solutions)
- https://redquark.org/leetcode/0005-longest-palindromic-substring/
RU
