某大厂算法笔试题，一模一样：要求时间复杂度在O(n)完成。

我采用的是递归，代码如下：

class Solution:

  def expandAroundCenter(self, s, left, right):

    while left >= 0 and right < len(s) and s[left] == s[right]:

      left -= 1

      right += 1

    return left + 1, right - 1

  def longestPalindrome(self, s: str) -> str:

    start, end = 0, 0

    for i in range(len(s)):

      left1, right1 = self.expandAroundCenter(s, i, i)

      left2, right2 = self.expandAroundCenter(s, i, i + 1)

      if right1 - left1 > end - start:

        start, end = left1, right1

      if right2 - left2 > end - start:

        start, end = left2, right2

    return s[start: end + 1]

思路其实很简单，主要想法就是分别对于奇偶讨论。这是因为，对于一个长度为2n+1的字符串是回文串。那么这个字符串的2n-1(去掉前后也一定是回文串）。所以就分为奇偶分别讨论。

每个长度为1的字符串一定是回文子串，同时长度为2的回文子串一定前后相等。

而所有的回文子串就是每个回文子串判断前后字母是否相等，直到不相等的时候。所以分别要从最小的回文子串进行判断，所以对于

   for i in range(len(s)):

      left1, right1 = self.expandAroundCenter(s, i, i)

      left2, right2 = self.expandAroundCenter(s, i, i + 1)

这一步是分别对奇偶取中心，判断1以i为中心与以i与i+1为中心的子串最长是什么样子的。同时用end，start记录最长。最后返回。

本算法的时间复杂度为n^2，空间复杂度为1.

同时还有一个时间复杂度更低的算法。这个算法是如何实现的呢？我们留到明天为大家讲解