s = 'AAAAA'
n = len(s)
dp = [[('', 0, 0) for i in range(n + 1)] for j in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        last = dp[i - 1][j - 1]
        if last[2] != i != j != last[1] and s[i - 1] == s[j - 1]:
            dp[i][j] = last[0] + s[i - 1], i, j
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], key=lambda t: len(t[0]))

print(dp[n][n][0])