Robert Eisele
Engineer, Systems Architect and DBA

Codefights: Is Permutation Of

Original Problem

Determines if leftString is a permutation (rearrangement of characters) of the rightString. If so, return true; otherwise return false.

Example

For leftString = "abc" and rightString = "bca", the output should be

IsPermutationOf(leftString, rightString) = true.

Input/Output

  • [time limit] 4000ms (js)
  • [input] string leftString

    The left string to be checked.

  • [input] string rightString

    The right string to be checked.

  • [output] boolean

    Returns true if leftString is a permutation of rightString (and, of course, vice versa) and false otherwise.

Solution

xor-ing the ASCII values of a string results in a certain checksum value. As the order of the arguments to xor does not matter, the same value will emerge for an arbitrary permutation. When the same string is xor'ed twice, the result must be zero - which is equivalently true for a permutation.

If we want to check if two strings are permutations of each other, all we have to do is make sure the length is the same and check if the concatenated xor-checksum is zero.

Using the Buffer and the spread-operator again allows a fairly compact solution:

IsPermutationOf = (l, r) =>
   l.length == r.length && ![...Buffer(r + l)].reduce((p, c) => p ^ c)

When we think about the length check, which consumes quite a few bytes, the only way to produce false positives is by adding test cases with an even number of additional characters on one string. Luckily, the questioner did not add such cases, which allows us to remove the check in order to pass the problem:

IsPermutationOf = (l, r) =>
   ![...Buffer(r + l)].reduce((p, c) => p ^ c)

That's short but not satisfying at all, since we lost the generality. But we can think differently about the problem: If we would sort the characters of each string and compare the resulting strings again, we would have a solid check again. So

_ = x => "" + x.split``.sort()
IsPermutationOf = (l, r) => _(l) == _(r)

We can save some more bytes by using the spread operator on strings again:

_ = x => "" + [...x].sort()
IsPermutationOf = (l, r) => _(l) == _(r)

Go to overview