/*Declare an array of 4 pointers to char representing 4 strings. Input 4 strings
//from the user after properly allocating space for them 
//Now, for each string, print whether it is a grouped word.

//Get rid of the strings that are not grouped words. For the remaning ones,
//output a permutation of concatenation that produce a grouped word. Note that,
//the permutation of concatenation here should involve all the remaining strings
//and not a subset*/
// Author:rahule@iitk.ac.in

#include<stdio.h>
#include<stdlib.h>
int string_length(char *s);		//function to find string length
char * string_concat(char *,char *);	//FUNCTION TO CONCATINATE TWO STRINGS AND RETURN POINTER TO THE NEW STRING
main()
{
  char *a[4],*s;
  int i,size,j,k,flag[4]={1,1,1,1},f=1;
  printf("Enter four strings togather with its expected size\n");
  for(i=0;i<4;i++)
  {
    printf("\nString %d Expected size :",i+1);
    scanf("%d",&size);
    a[i]=malloc(size);
    printf("Enter the string %d :",i+1);
    scanf("%s",a[i]);
  }
  
  for(i=0;i<4;i++)
  {
    flag[i]=chk_grup_word(a[i]);	//chk_grup_word returns 1 if the string passed is an grouped word
  }
  
  for(i=0;i<4;i++)			//printing whetehr the ith string is group word or not.
  {
    if(flag[i]==1)
      printf("\n'%s' is a grouped word",a[i]);
    else
      printf("\n'%s' is NOT a grouped word",a[i]);
  }
  
  //////////////////////////  Appending the group words found  /////////////////////////
  
  //Phase 1: Check whethr if there are any two strings i,j SuchThat i starts with ending character of string j(or vice versa).If yes,concatenate the two strings and
  //check whethr they still follows the properties of grouped words   ;Eg: aapppp AND tttaaa  (or kkkkpp AND ppsss)
  for(i=0;i<4;i++)
  {
    if(flag[i]==0) continue;		//choose a string a[i],which is a grouped word
    
    for(j=0;j<4;j++)
    {
      if(i==j || flag[j]==0) continue;	////choose a string a[j],which is a grouped word

      if(a[i][string_length(a[i])-1] == a[j][0])	//check whether last character if a[i] is same as the first charecter of a[j]
      {
	a[i]=string_concat(a[i],a[j]);			//if yes,concatenate them and store the resulting string at i
	flag[j]=0;		// indicates,j is no longer relevent (since it has been appended to i)
	if(!chk_grup_word(a[i]))//check the appended string is still a valid grouped word
	{
	  printf("\nNO");	//if not,given set of strings can not be combined any way to get a grouped word
	  exit(0);		//terminates the program
	}
      }
    }
  }
  
  
  //Phase 2:Since we have already appeneded strings having common starting and ending characters,we can now combine the remaining strings in any order.(order doesnt matter)
  
  for(i=0;i<4;i++)	//find the fisrt string which is a grouped word and stores in s
  {
    if(flag[i]==1)
    {
      s=a[i];
      break;
    }
  }
  
  for(j=i+1;j<4;j++)		//when ever we come across a grouped word,combine it with s
  {
    if(flag[j]==1 )
    {
      s=string_concat(s,a[j]);
    }
  }
  if(chk_grup_word(s))		//check whether the resulting string is still grouped word
    printf("\n%s\n",s);
  else
    printf("\nNO\n");
}

int string_length(char *s)
//funtion to find the string length
{
  int i;
  for(i=0;s[i]!='\0';i++);	//loop till the end of string
  return(i);
}


char * string_concat(char *s1,char *s2)
//function to conatenate two strings s1,s2 and returns the pointer to the new string
{
  int i,j;
  char *s=(char *)malloc(string_length(s1)+string_length(s2)+1);	//creates necessary space (array)
  for(i=0;s1[i]!='\0';i++)	//copies fisrt string to newly created array
    s[i]=s1[i];
  
  for(j=0;s2[j]!='\0';j++)	//copies second string to newly created array
  {
    s[i]=s2[j];
    i++;
  }
  s[i]='\0';			//appends a '\0' to make it a valid string
  return(s);			//returns a pointer to the string
}
int chk_grup_word(char *s)
//function to check whether a given string s is grouped word or not
{
  int j,k;
  for(j=0;j<string_length(s)-1;j++)	//for each character a[j],
    {
      if(s[j]!=s[j+1])		//if a[j] is not the same as the next character ,ie a[j+1]
      {
	for(k=j+1;k<string_length(s);k++)	//then check whethr a[j] repeats anywhere in the remaining string
	{
	  if(s[j]==s[k])
	  {
	    return(0);			//if a[j] repeats later,retun 0
	  }
	}
      }
    }
    return(1);		//if control reaches here,then the stroing is grouped word!
}