Palindrome

import fileinput


def lp(s):
    n = len(s)
    t = [[False for i in range(n)] for j in range(n)]
    for i in range(n):
        t[i][i] = True
    st = 1
    ml = 1
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            t[i][i + 1] = True
            st = i
            ml = 2
    for k in range(3, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if t[i + 1][j - 1] == True and s[i] == s[j]:
                t[i][j] = True
                if k > ml:
                    st = i
                    ml = k
    return s[st:st + ml]

with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    print(lp(seq))

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED