Hints to solve the problem

help
, ,
1

problem link

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

2
  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.

Final answer = dp[n][n][1]

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][1] = inf; 
            dp[i][j][2] = inf; 
            if(!i || !j)continue;
            if(s[i-1] == t[j-1] && s[i-1] != c){
                dp[i][j][0] = dp[i-1][j-1][0] + 1; 
                if(dp[i-1][j-1][1] != inf)dp[i][j][1] = dp[i-1][j-1][1] + 1;
                if(dp[i-1][j-1][2] != inf)dp[i][j][2] = dp[i-1][j-1][2] + 1;
            }
            else if(s[i-1] == t[j-1] && s[i-1] == c){
                if(dp[i-1][j-1][1] != inf)
                    dp[i][j][1] = max(dp[i-1][j-1][1],dp[i-1][j-1][0])+1;
                else
                    dp[i][j][1] = dp[i-1][j-1][0] + 1;
                if(dp[i-1][j-1][1] != inf && dp[i-1][j-1][2] != inf)
                    dp[i][j][2] = max(dp[i-1][j-1][1],dp[i-1][j-1][2])+1;
                else if(dp[i-1][j-1][1] != inf)
                    dp[i][j][2] = dp[i-1][j-1][1] + 1;
                dp[i][j][0] = max(dp[i-1][j][0],dp[i][j-1][0]); 
            }
            else if(s[i-1] != t[j-1]){
                dp[i][j][0] = max(dp[i-1][j][0],dp[i][j-1][0]);
                if(dp[i-1][j][1] != inf && dp[i][j-1][1] != inf)
                    dp[i][j][1] = max(dp[i-1][j][1],dp[i][j-1][1]);
                else if(dp[i-1][j][1] != inf)
                    dp[i][j][1] = dp[i-1][j][1];
                else if(dp[i][j-1][1] != inf)
                    dp[i][j][1] = dp[i][j-1][1];
                if(dp[i-1][j][2] != inf && dp[i][j-1][2] != inf)
                    dp[i][j][2] = max(dp[i-1][j][2],dp[i][j-1][2]);
                else if(dp[i-1][j][2] != inf)
                    dp[i][j][2] = dp[i-1][j][2];
                else if(dp[i][j-1][2] != inf)
                    dp[i][j][2] = dp[i][j-1][2];
            }
        }
    }
    if(dp[n][n][2] == inf)dp[n][n][2] = 0;
    if(dp[n][n][1] != inf && dp[n][n][1] % 2)dp[n][n][2] = max(dp[n][n][2],dp[n][n][1]);
    cout << dp[n][n][2] << "\n";
}
 
int main(){
    int t;
    cin >> t;
    while(t--)solve();
    return 0;
}
3 Likes
3

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

4

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