def solve(S):
    H = dict()

    def f(i, j):
        if j <= i:
            return ''

        if j - i == 1:
            return S[i]

        if (i, j) in H:
            return H[(i, j)]

        if S[i] == S[j - 1]:
            H[(i, j)] = S[i] + f(i + 1, j - 1) + S[j - 1]
        else:
            c1 = f(i + 1, j)
            c2 = f(i, j - 1)
            H[(i, j)] = c1 if len(c1) > len(c2) else c2

        return H[(i, j)]

    return f(0, len(S))


print(solve('abcba'))
print(solve('ababz'))
print(solve('aca'))
print(solve('abcde'))