/// hi_im_manh :D #include <bits/stdc++.h> #define reset(a,n) memset(a,0,(n+1)*sizeof(int)) #define endl "\n" #define llmin LLONG_MIN #define llmax LLONG_MAX #define intmax INT_MAX #define intmin INT_MIN #define ll long long #define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL) #define duckman "TASK" #define input freopen(duckman".inp", "r", stdin); #define output freopen(duckman".out", "w", stdout); #define nmax 22000 using namespace std; int main() { fast; // input; // output; string x; cin >> x; int n = x.size(); int dp[n][n]; for (int r = 0; r < n; ++r) { for (int l = r; l >= 0; --l) { int len = r-l+1; if (x[l] == x[r]) { if (len <= 3) { dp[l][r] = len; } else { dp[l][r] = dp[l+1][r-1] + 2; } } else { dp[l][r] = max(dp[l+1][r], dp[l][r-1]); } } } int r = dp[0][n-1] - 1, l = 0; char ans[r+2] = {'\0'}; int i = 0, j = n-1; while (i <= j) { if (x[i] == x[j]) { ans[l++] = ans[r--] = x[i]; ++i; --j; } else if (dp[i][j] == dp[i+1][j]) { ++i; } else { --j; } } cout << ans; return 0; } /* */