1326D1. Prefix - Codeforces Solution C++ ~ CodingWithArt

➤ 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!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.