def is_plalindrome(string):  return string == ''.join(list(reversed(string)))`

def is_plalindrome(string):
  string = list(string)
  length = len(string)
  left = 0
  right = length - 1
  while left < right:
    if string[left] != string[right]:
      return False
    left += 1
    right -= 1
  return True

def solution(s):
  s = list(s)
  l = len(s)
  dp = [[0] * l for i in range(l)]
  for i in range(l):
    dp[i][i] = True
    # 当 k = 2时要用到
    dp[i][i - 1] = True
  resLeft = 0
  resRight = 0
  # 枚举子串的长度
  for k in range(2, l+1):
    # 子串的起始位置
    for i in range(0, l-k+1):
      j = i + k - 1
      if s[i] == s[j] and dp[i + 1][j - 1]:
        dp[i][j] = True
        # 保存最长的回文起点和终点
        if resRight - resLeft + 1 < k:
          resLeft = i
          resRight = j
  return ''.join(s[resLeft:resRight+1])

char: # a # b # a #
RL:  1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i:   0 1 2 3 4 5 6
char: # a # b # a # b #
RL:  1 2 1 4 1 4 1 2 1
RL-1: 0 1 0 3 0 3 0 1 0
i:  0 1 2 3 4 5 6 7 8

def manacher(preS):
  s = '#' + '#'.join(preS) + '#'
  l = len(s)
  RL = [0] * l
  maxRight = pos = maxLen = 0
  for i in range(l):
    if i < maxRight:
      RL[i] = min(RL[2*pos - i], maxRight-i)
    else:
      RL[i] = 1
    while i - RL[i] >= 0 and i + RL[i] < l and s[i - RL[i]] == s[i + RL[i]]:
      RL[i] += 1
    if i + RL[i] - 1 > maxRight:
      maxRight = i + RL[i] - 1
      pos = i
  maxLen = max(RL)
  idx = RL.index(maxLen)
  sub = s[idx - maxLen + 1: idx + maxLen]
  return sub.replace('#', '')

abbabbc => abbc
abababb => ababa
sogou => s

def longest_palindrome_prefix(s):
  if not s:
    return 0
  s = s + '#' + s[::-1] + '$'
  i = 0
  j = -1
  nt = [0] * len(s)
  nt[0] = -1
  while i < len(s) - 1:
    if j == -1 or s[i] == s[j]:
      i += 1
      j += 1
      nt[i] = j
    else:
      j = nt[j]
  return nt[len(s) - 1]

aacecaaa -> aaacecaaa # 添加 a
abcd -> dcbabcd # 添加 dcb

def solution(s):
  length = longest_palindrome_prefix(s)
  return s[length:][::-1] + s

# 求得最长回文子序列的长度
def solution(s):
  l = len(s)
  dp = [[0] * l for i in range(l)]
  for i in range(l):
    dp[i][i] = 1
  # 枚举子串的长度
  for k in range(2, l+1):
    # 枚举子串的起始位置
    for i in range(0, l-k+1):
      j = i + k - 1
      if s[i] == s[j]:
        dp[i][j] = dp[i + 1][j - 1] + 2
      else:
        dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
  return dp[0][l-1]