➤ Problem Link : 1326D1. Prefix
✅ C++ Solution :
#include<bits/stdc++.h> using namespace std; #define ll long long int #define m 998244353 int main() { int t; cin>>t; while(t--) { string s; cin>>s; int n=s.length(); int j=0; while(j<n-j-1 && s[j]==s[n-j-1]) j++; if(j==n-j-1) { cout<<s<<endl; continue; } bool dp[n][n]; memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) dp[i][i]=1; int pi,pj; int len=0; for(int k=1;k<n;k++) { int i,j; for(i=0,j=k;i<n && j<n;i++,j++) { if(k==1) { if(s[i]==s[j]) dp[i][j]=1; } else if(s[i]==s[j] && dp[i+1][j-1]) dp[i][j]=1; } } int k=j; for(int p=k;p<=n-j-1;p++) { if(dp[k][p] && p-k+1 > len) { len=p-k+1; pi=k; pj=p; } if(dp[p][n-j-1] && n-j-p > len) { len = n-j-p; pi=p; pj=n-j-1; } } // cout<<dp[2][3]<<endl; // cout<<j<<" "<<pi<<" "<<pj<<endl; string ans=""; ans+=s.substr(0,j); if(len>0) ans+=s.substr(pi,pj-pi+1); ans+=s.substr(n-j,j); cout<<ans<<endl; } }
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!