Construct Square

Description

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] 4 seconds (js)
[input] string s

Guaranteed constraints:
1 ≤ s.length < 10.
[output] integer

[JavaScript (ES6)] Syntax Tips

1
2
3
4
5
6
// Prints help message to the console
// Returns a string
function helloWorld(name) {
console.log("This prints to the console when you Run Tests");
return "Hello, " + name;
}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function constructSquare(s) {
  var min = Number(
    "1" +
      Array(Math.floor((s.length - 1) / 2))
        .fill(0)
        .join("")
  );
  var max = Number(
    Array(Math.ceil(s.length / 2))
      .fill(9)
      .join("")
  );
  var d = getDigitsCount(s);
  for (var i = max + 1; i >= min - 1; i--) {
    if (getDigitsCount(String(i * i)) === d) return i * i;
  }
  return -1;

  function getDigitsCount(str) {
    var d = [];
    while (str.length) {
      var c = str[0];
      d.push(str.length - (str = str.replace(new RegExp(c, "g"), "")).length);
    }
    return d.sort((a, b) => b - a).join("");
  }
}

Codefights

A way to improve your programming skills.

Construct Square

Description

Solution