# Hints to solve the problem

I am unable to think how to solve this problem. Help please.

1. Learn longest common subsequence.
2. Find LCS of String A and Reverse(String A)

Oh sorry I missed character C point.

for character C maintain 3rd dimension in dp as well for including character C, without including character C.

Update: I went ahead and solved this question. I was wrong, it required 3 states for last dimension, 0: not included, 1 once included, 2 atleast twice included

Reason for third dimension would be testcases like these

m
wmlkpcsewczamlpxkr

Code for reference
``````
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
void solve(){
char c;
string s;
cin >> c >> s;
int n = s.size();
string t = s;
reverse(s.begin(),s.end());
vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(n+1,vector<int>(3,0)));
for(int i = 0; i <= n; ++i){
for(int j = 0; j <= n; ++j){
dp[i][j] = inf;
dp[i][j] = inf;
if(!i || !j)continue;
if(s[i-1] == t[j-1] && s[i-1] != c){
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i-1][j-1] != inf)dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i-1][j-1] != inf)dp[i][j] = dp[i-1][j-1] + 1;
}
else if(s[i-1] == t[j-1] && s[i-1] == c){
if(dp[i-1][j-1] != inf)
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j-1])+1;
else
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i-1][j-1] != inf && dp[i-1][j-1] != inf)
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j-1])+1;
else if(dp[i-1][j-1] != inf)
dp[i][j] = dp[i-1][j-1] + 1;
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
else if(s[i-1] != t[j-1]){
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
if(dp[i-1][j] != inf && dp[i][j-1] != inf)
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
else if(dp[i-1][j] != inf)
dp[i][j] = dp[i-1][j];
else if(dp[i][j-1] != inf)
dp[i][j] = dp[i][j-1];
if(dp[i-1][j] != inf && dp[i][j-1] != inf)
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
else if(dp[i-1][j] != inf)
dp[i][j] = dp[i-1][j];
else if(dp[i][j-1] != inf)
dp[i][j] = dp[i][j-1];
}
}
}
if(dp[n][n] == inf)dp[n][n] = 0;
if(dp[n][n] != inf && dp[n][n] % 2)dp[n][n] = max(dp[n][n],dp[n][n]);
cout << dp[n][n] << "\n";
}

int main(){
int t;
cin >> t;
while(t--)solve();
return 0;
}
``````
3 Likes

thanq the update part is hard but i will try to solve

If you check other’s solution they have solved it with an easier recursive method, which I will prefer over my own code.