<Codesignal> stringsRearrangement

Medium

Given an array of equal-length strings, you'd like to know if it's possible to rearrange the order of the elements in such a way that each consecutive pair of strings differ by exactly one character. Return true if it's possible, and false if not.

Note: You're only rearranging the order of the strings, not the order of the letters within the strings!

Example

• For inputArray = ["aba", "bbb", "bab"], the output should be
  stringsRearrangement(inputArray) = false.

  There are 6 possible arrangements for these strings:

  • ["aba", "bbb", "bab"]
  • ["aba", "bab", "bbb"]
  • ["bbb", "aba", "bab"]
  • ["bbb", "bab", "aba"]
  • ["bab", "bbb", "aba"]
  • ["bab", "aba", "bbb"]

  None of these satisfy the condition of consecutive strings differing by 1 character, so the answer is false.

• For inputArray = ["ab", "bb", "aa"], the output should be
  stringsRearrangement(inputArray) = true.

  It's possible to arrange these strings in a way that each consecutive pair of strings differ by 1 character (eg: "aa", "ab", "bb" or "bb", "ab", "aa"), so return true.

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] array.string inputArray

  A non-empty array of strings of lowercase letters.

  Guaranteed constraints:
  2 ≤ inputArray.length ≤ 10,
  1 ≤ inputArray[i].length ≤ 15.

• [output] boolean

  • Return true if the strings can be reordered in such a way that each neighbouring pair of strings differ by exactly one character (false otherwise).

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
bool stringsRearrangement(arr_string inputArray)
{
	int N=0;

	for(int i=0;i<inputArray.size;i++) 
	{
		int count=0;
		bool isSame=false;

		for(int j=0;j<inputArray.size;j++)
		{
			if(i==j)
				continue;
			int difference=0;

			for(int k=0;k<strlen(inputArray.arr[0]);k++)
				difference+=inputArray.arr[i][k]!=inputArray.arr[j][k];

			count+=difference==1;
		}

		for(int j=0;j<i;j++)
			if(strcmp(inputArray.arr[i],inputArray.arr[j])==0)
			{
				isSame=true;
				break;
			}

		if(count==0)
			return false;

		N+=isSame?count%3==count:count==1;
	}

	return N<=2;
}