leetcode

# 最长回文子串
class Solution:
    def longestPalindrome(self, s: str) -> str:
        return self.manacher(s)

    @staticmethod
    def manacher(s: str) -> str:
        # 如果s是单字符的字符串，那么直接返回
        if len(s) < 2:
            return s

        # 将一个可能是偶数长/奇数长的字符串，首位以及每个字符间添加#，确保添加后变成了长度为奇数的字符串
        manacher_length = len(s) * 2 + 1
        manacher_str = "#".join(s).center(manacher_length, "#")

        # 记录最长子回文串
        max_palindrome = ""
        for i in range(manacher_length):
            left = i - 1
            right = i + 1
            while left >= 0 and right < manacher_length and \
                    manacher_str[left] == manacher_str[right]:
                left -= 1
                right += 1

            # 将左右指针回退一位，得到本次遍历的回文串长度：(right - 1) - (left + 1) + 1 = right - left - 1
            if right - left - 1 > len(max_palindrome):
                max_palindrome = manacher_str[left + 1:right]

        # 由于max_palindrom是包含特殊字符#的回文子串，因此需要将#字符删除后返回
        return max_palindrome.replace("#", "")

# 自测用例
if __name__ == '__main__':
    s = Solution()
    result = s.longestPalindrome("abcbcba")
    print(result)