<Codesignal> Construct Square

Medium

Given a string consisting of lowercase English letters, find the largest square number which can be obtained by reordering the string's characters and replacing them with any digits you need (leading zeros are not allowed) where same characters always map to the same digits and different characters always map to different digits.

If there is no solution, return -1.

Example

• For s = "ab", the output should be
  constructSquare(s) = 81.
  The largest 2-digit square number with different digits is 81.
• For s = "zzz", the output should be
  constructSquare(s) = -1.
  There are no 3-digit square numbers with identical digits.
• For s = "aba", the output should be
  constructSquare(s) = 900.
  It can be obtained after reordering the initial string into "baa" and replacing "a" with 0 and "b" with 9.

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] string s

  Guaranteed constraints:
  1 ≤ s.length < 10.

• [output] integer

[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

int constructSquare(char *s)
{
	int l, N, end=sqrt(pow(10,strlen(s))-1), start=sqrt(pow(10,strlen(s)-1));
	bool solved;

	for(int i=end;i>=start;i--)
	{
		int A[128]={0, };
		int B[10]={0, };

		N=i*i;

		while(N!=0)
		{
			B[N%10]++;
			N/=10;
		}
		for(int j=0;j<strlen(s);j++)
			A[s[j]]++;

		solved=true;

		for(int k=0;k<128;k++)
		{
			if(A[k]==0)
				continue;

			for(l=0;l<10;l++)
				if(A[k]==B[l])
				{
					B[l]=0;
					break;
				}

			if(l==10)
			{
				solved=false;
				break;
			}
		}

		if(solved)
			return i*i;
	}

	return -1;
}