Hackerrank: Making Anagrams

I’ve put together some sample solutions to the Hackerrank String: Making Anagrams challenge using JavaScript on Node.js.

I’m really enjoying tackling some (pretty easy) challenges on hackerrank.com. It’s been fun to think through the challenges and possible solutions, and I’ve enjoyed thinking about different solutions to the same problem. If you want you can also check out my solutions to the array left rotation challenge

In this challenge we are working with anagrams, well, actually we are trying to determine the minimum number of letters that must be removed from two strings to make an anagram. Here is the overview from hackerrank:

Given two strings, a and b, that may or may not be of the same length, determine the minimum number of character deletions required to make a and b anagrams. Any characters can be deleted from either of the strings.

The progam tests expect a single integer output: the number of characters that must be deleted.

Source

You can download the source code and follow along or fork the repository on GitHub:

Input

As given, the input is two lines of character strings representing a and b. I created a new text file named data.txt that will represent the input to my program:

ilovea
challenge

With this given input our anagram is simply: ael. That means that the following letters will be removed: iov from the first string and chlnge from the second string. The answer is: 9 characters need to be deleted from both strings to form the anagram.

I then wrote some code using Node.js to read and parse the data:

//global variables
let a = '';
let b = '';

//read standard input
process.stdin.setEncoding('utf8');
process.stdin.resume();

//store input
let input = '';
process.stdin.on('data', function (data) {
  input += data;
});
process.stdin.on('end', function () {
  let linesOfInput = input.split('\n');
  a = linesOfInput[0];
  b = linesOfInput[1];
  main();
});

//let's do it
function main() {
  //verify values
  if (String(a) !== a || String(b) !== b || a.length === 0 || b.length === 0) {
    throw Error('The input values are invalid.');
  }

  //get result
  //result will be a Number

  //output
  process.stdout.write(result.toString());
}

First I define some global variables to represent our inputs: a and b.

I then read the input in via standard input and split the data on the newline character. After saving the a and b strings I invoke my main() function.

In the main() function I first validate the input. Then we will invoke a method to return our result, which will be a number. Finally, we output the string using standard output.

First: `indexOf()`

The first approach I took will take advantage of the Array.prototype.indexOf() method.

function getDeleteCountUsingIndexOf() {
  var aChars = a.split('');
  var bChars = b.split('');

  if (aChars.length > bChars.length) {
    var outer = aChars;
    var inner = bChars;
  } else {
    var outer = bChars;
    var inner = aChars;
  }

  var outerIndex = outer.length - 1;
  while (inner.length > 0 && outer.length > 0 && outerIndex >= 0) {
    let innerIndex = inner.indexOf(outer[outerIndex]);
    if (innerIndex !== -1) {
      outer.splice(outerIndex, 1);
      inner.splice(innerIndex, 1);
    }
    --outerIndex;
  }

  return outer.length + inner.length;
}

First, I use the String.prototype.split() method to split the string into an array of characters. I then determine the outer (or larger array) and inner (shorter) arrays.

I will keep track of my position within the outer array using outerIndex, decrementing it after each iteration. While iterating from the end of the outer array I look for the same character in the inner array. If the character exists then I remove the character from both the outer and inner arrays.

The while-loop continues until either array is empty (has a length of 0) or the outerIndex is 0.

Second: Destructive

My next approach uses a while-loop destructive approach. The one drawback to this approach is that in order for this to work I will need to alphabetically sort the array of characters. Using the Array.prototype.sort() method we can provide a sorting function to sort our arrays. I implement this in a separate function named getSortedArrayofChars(str), which accepts a single string argument and returns the sorted array of characters.

function getDeleteCountUsingDestructive() {
  let aChars = getSortedArrayofChars(a);
  let bChars = getSortedArrayofChars(b);

  var letters = [];
  while (aChars.length > 0 || bChars.length > 0) {
    //check if aChars array is empty
    if (aChars.length === 0) {
      letters.push(bChars.shift());
      continue;
    }

    //check if bChars array is empty
    if (bChars[0] === undefined) {
      letters.push(aChars.shift());
      continue;
    }

    //shift first element based on ascii comparison
    if (aChars[0] < bChars[0]) {
      letters.push(aChars.shift());
    } else if (aChars[0] > bChars[0]) {
      letters.push(bChars.shift());
    } else {
      aChars.shift();
      bChars.shift();
    }
  }

  return letters.length;
}

function getSortedArrayofChars(str) {
  //get the array of characters using array.split()
  let arrayOfChars = str.split('');

  //sort the array alphabetically
  let alphabetically = (a, b) => {
    a = a.toLowerCase();
    b = b.toLowerCase();
    if (a < b) {
      return -1;
    } else if (a > b) {
      return 1;
    }
    return 0;
  };
  return arrayOfChars.sort(alphabetically);
}

Let’s break this down:

The while-loop iterates until both arrays aChars and bChars are empty.
We will build an array of letters that contains the characters that will need to be removed from either string a or b in order to make an anagram.
Within the loop I check if either array is empty. If aChars array is empty then all of the characters left in the bChars are pushed onto the letters (as they will need to be removed to form the anagram). And vice versa for the bChars array.
If the character at position 0 of the aChars array is less (lexographically using Unicode) than the character at position 0 in the bChars array (e.g. a is less than b) then we use Array.prototype.shift() to remove the element at position 0 in the aChars array and to store this value in our letters array.
Likewise, if the aChars[0] is greater-then bChars[0] (e.g. b is greater than a) then we remove the first element in bChars and save this in letters.
If the characters match (e.g. a is equal to a) then we can simple remove the first element in each array.
Once both aChars and bChars are empty (destroyed) then we return the number of letters that need to be deleted.

Further Explanation

To help understand the destructive approach let’s take a look at the following values upon each iteration of the while-loop:

aChars - sorted array of characters in given string a
bChars - sorted array of characters in given string b
letters - array of letters (characters) that need to be deleted to make an anagram.

Remember our input was:

ilovea
challenge

So, the initial value of each array is:

aChars = [ 'a', 'e', 'i', 'l', 'o', 'v' ]
bChars = [ 'a', 'c', 'e', 'e', 'g', 'h', 'l', 'l', 'n' ]
letters = []

Here is the result of logging the values of each array at the end of each iteration:

aChars:   [ 'e', 'i', 'l', 'o', 'v' ]
bChars:   [ 'c', 'e', 'e', 'g', 'h', 'l', 'l', 'n' ]
letters:  []
 --
aChars:   [ 'e', 'i', 'l', 'o', 'v' ]
bChars:   [ 'e', 'e', 'g', 'h', 'l', 'l', 'n' ]
letters:  [ 'c' ]
 --
aChars:   [ 'i', 'l', 'o', 'v' ]
bChars:   [ 'e', 'g', 'h', 'l', 'l', 'n' ]
letters:  [ 'c' ]
 --
aChars:   [ 'i', 'l', 'o', 'v' ]
bChars:   [ 'g', 'h', 'l', 'l', 'n' ]
letters:  [ 'c', 'e' ]
 --
aChars:   [ 'i', 'l', 'o', 'v' ]
bChars:   [ 'h', 'l', 'l', 'n' ]
letters:  [ 'c', 'e', 'g' ]
 --
aChars:   [ 'i', 'l', 'o', 'v' ]
bChars:   [ 'l', 'l', 'n' ]
letters:  [ 'c', 'e', 'g', 'h' ]
 --
aChars:   [ 'l', 'o', 'v' ]
bChars:   [ 'l', 'l', 'n' ]
letters:  [ 'c', 'e', 'g', 'h', 'i' ]
 --
aChars:   [ 'o', 'v' ]
bChars:   [ 'l', 'n' ]
letters:  [ 'c', 'e', 'g', 'h', 'i' ]
 --
aChars:   [ 'o', 'v' ]
bChars:   [ 'n' ]
letters:  [ 'c', 'e', 'g', 'h', 'i', 'l' ]
 --
aChars:   [ 'o', 'v' ]
bChars:   []
letters:  [ 'c', 'e', 'g', 'h', 'i', 'l', 'n' ]
 --
aChars:   [ 'v' ]
bChars:   []
letters:  [ 'c', 'e', 'g', 'h', 'i', 'l', 'n', 'o' ]
 --
aChars:   []
bChars:   []
letters:  [ 'c', 'e', 'g', 'h', 'i', 'l', 'n', 'o', 'v' ]

As you can see we iteratively destroy the aChars and bChars arrays and store an array of letters that need to be removed from the array.

Source

You can download the source code or fork the repository on GitHub:

Executing

Executing the solution is easy:

$ node making-anagrams.js < data.txt

Source

Input

First: indexOf()

Second: Destructive

Further Explanation

Source

Executing

First: `indexOf()`