Transform to Palindrome | Editorial by aksingh007

The problem could be solved using DSU data-structure. Here we perform the union and replace all the characters by their representative character of their set.
Now find the longest palindrome using DP.

```
//MATCHING SUB-STRING O(n*m)/O(n+m)
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define LL long long
#define and &&
#define or ||
#define max(a,b) (a>b)?a:b;
#define s(n) scanf("%lld",&n)
#define ss(n,m) scanf("%lld%lld",&n,&m)
#define sss(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define size 1000000

struct nodes{
	LL int vertex;
	LL int parent;        //STORES_THE_NODE_DETAILS
	LL int rank;
}node[size];

int find_set(int a){
	int pa;
	pa=node[a].parent;
		while(1){
			if(node[pa].parent==pa)
				break;                 //   FINDING_PARENT_OF_a;
			else
				pa=node[pa].parent;
		}
		node[a].parent=pa;           //APPLYING_PATH_COMPRESSION;
	return(pa);
}

void union_set(int pa,int pb){
	int ra,rb;
	ra=node[pa].rank;
	rb=node[pb].rank;                          /*   WORK ON RANK  */
	  if(ra==rb){
			node[pb].parent=pa;
			(node[pa].rank)++;
			}
			else 
				if(ra>rb){
				node[pb].parent=pa;
			}
			else
			{
				node[pa].parent=pb;
			}
	
	return;
}

int* convert(int *arr,int m){
	int i=0,j=m-1;
    for(i=0;i<m;i++)
	   arr[i]=find_set(arr[i]);
	return arr;
}
int lps(int *str,int n)
{

int i, j, cl;
int L[n][n]; 
for (i = 0; i < n; i++)
	L[i][i] = 1;
	for (cl=2; cl<=n; cl++)
	{
		for (i=0; i<n-cl+1; i++)
		{
			j = i+cl-1;
			if (str[i] == str[j] && cl == 2)
			L[i][j] = 2;
			else if (str[i] == str[j])
			L[i][j] = L[i+1][j-1] + 2;
			else
			L[i][j] = max(L[i][j-1], L[i+1][j]);
		}
	}

return L[0][n-1];
}

int main(){
	int n,k,m,x,y,a0,a_i,pa,pb,i;
    
    scanf("%d %d %d", &n, &k, &m);
	for(i=1;i<=n;i++){
			node[i].vertex=i;
			node[i].parent=i;
			node[i].rank=0;
		}
    for(a0 = 0; a0 < k; a0++){
        scanf("%d %d", &x, &y);
		pa=find_set(x);
		pb=find_set(y);
		//printf("1:%d %d\n",pa,pb);
		union_set(pa,pb);
		//printf("2:%d %d\n",pa,pb);
    }
    int *arr = malloc(sizeof(int) * m);
    for(a_i = 0; a_i < m; a_i++){
       scanf("%d",&arr[a_i]);
    }
	arr=convert(arr,m);
	//for(a_i = 0; a_i < m; a_i++)
      // printf("%d ",find_set(arr[a_i]));
  
	int ans=lps(arr,m);
	printf("%d\n",ans);
    return 0;
}

/*
CRITICAL INPUT
1
4 4
1 2 1
2 4 1
1 3 2
3 4 1
*/

```

Transform to Palindrome | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?