Google Kick Start回文匹配题实现遇边界问题及超时求指导

刚结束Google Kick Start Round E赛事，我在实现Palindrome Matching（回文匹配）题目时遇到两个问题：一是始终找不到代码遗漏的边界用例，导致代码卡在第二个检查点；二是初始尝试的代码出现超时错误，但奇怪的是它能通过第二个尝试无法通过的用例，我找不到两者的差异。

题目描述 #

给定一个长度为N、仅由小写英文字母组成的回文字符串P，找到最短的非空回文字符串Q，使得P与Q拼接后的字符串PQ是回文。

输入输出要求 #

• 输入：第一行是测试用例数T，每个测试用例包含两行，第一行是字符串P的长度N，第二行是回文字符串P。
• 输出：每个测试用例输出Case #x: y，其中x是测试用例编号（从1开始），y是满足要求的Q。

卡住检查点的代码 #

我的思路是遍历给定回文串，判断能否在当前索引处将其拆分为两个回文串，第一个符合条件的拆分对应的前缀即为最短Q。但以下代码卡在第二个检查点：

import fileinput

cases = 0
total_cases = 0
length = 0

def check_palindrome(st,en, s):
    while(st < en):
        if s[st] == s[en]:
            st += 1
            en -=1
        else:
            return False
    return True

def solve(s):
    for i in range(1,len(s) - 1):
        if check_palindrome(i, len(s) - 1, s) and check_palindrome(0, i - 1, s):
            return s[0:i]
    return s

for line in fileinput.input():
    if fileinput.isfirstline():
        total_cases = int(line.strip())
        continue
    elif cases == total_cases:
        break
    else:
        if fileinput.lineno() % 2 == 0:
            length = int(line.strip())
        else:
            s = solve(line.strip())
            cases += 1
            print(f'Case #{cases}: ' + s)

超时但能过部分用例的初始代码 #

初始尝试的代码出现了超时错误，但它能通过上面代码无法通过的用例，我找不到两者的差异：

def check_palindrome(st,en, s):
    while(st < en):
        if s[st] == s[en]:
            st += 1
            en -=1
        else:
            return False
    return True

def solve(s):
    st= 1
    sol = s[0]
    while(st < len(s)):
        if check_palindrome(st, len(s) - 1, s) and check_palindrome(0, len(sol) - 1, sol):
            return sol
        else:
            sol = s[st] + sol
            st += 1
    return sol

希望有人能指出问题所在并给出优化方向。

内容的提问来源于stack exchange，提问作者genchemmer1234