Brian F Love
Learn from a Google Developer Expert focused on Angular, Web Technologies, and Node.js from Portland, OR.

# 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.

## 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 = '';

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;
b = linesOfInput;
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 === undefined) {
letters.push(aChars.shift());
continue;
}

//shift first element based on ascii comparison
if (aChars < bChars) {
letters.push(aChars.shift());
} else if (aChars > bChars) {
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` is greater-then `bChars` (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``

### Brian F Love

Hi, I'm Brian. I am interested in TypeScript, Angular and Node.js. I'm married to my best friend Bonnie, I live in Portland and I ski (a lot).