Untitled

#include<bits/stdc++.h>
using namespace std;

int n, m; string s1, s2;
vector<vector<int>> dp;
int LCS(int m, int n)
{
    if (m == 0 || n == 0) return 0;

    if (dp[m][n] != -1) return dp[m][n];

    if (s1[m - 1] == s2[n - 1]) return dp[m][n] = 1 + LCS(m - 1, n - 1);

    return dp[m][n] = max(LCS(m - 1, n), LCS(m, n - 1));
}
int main()
{
    cin >> s1;
    s2 = s1;
    m = n = s1.size();
    dp.assign(m + 1, vector<int>(n + 1 , -1));
    reverse(s2.begin(), s2.end());
    cout<< LCS(m,n);
}