# HackerRank Making Anagrams solution with JavaScript

Learn how to solve the making anagrams problem from the HackerRank challenges by using JavaScript strings, loops, objects, and counters.
May 02, 2023JavaScript

Let's learn how to solve the Making Anagrams challenge from the HackerRank website.

This challenge states that two strings are anagrams of each other if both strings contain the same exact letters in the same exact frequency. The strings `bacdc` and `dcbac` are anagrams, but the strings `bacdc` and `dcbad` are not anagrams.

The challenge goes on to explain that Alice has decided on an encryption scheme where the encryption depends on the minimum number of character deletions needed to make two strings anagrams.

Given two strings that may not be of the same length, we need to help Alice determine the number of character deletions necessary to make two strings anagrams. We can delete any characters from either of the strings to make the anagram happen.

## Pseudo code solution

1. Create an `s1_differences` object to track the characters that are only unique to the `s1` string. The keys will be the characters and the values will be how many times the characters occur. Each occurrence will need to be deleted.
2. Create a `unique_to_s2` variable to track the number of characters that are only unique to the `s2` string. They'll need to be deleted.
3. Loop over characters in the `s1` string, assuming every character is only unique to the `s1` string.
• If a character is not yet in `s1_differences`, add it as a key and set the value to `1` for its first occurrence.
• If a character is already in `s1_differences`, increment its number of occurrences by `1`.
4. Loop over characters in the `s2` string.
• If an `s2` character is already in `s1_differences`, decrement its associated value since its one less difference between `s1` and `s2`. No character deletion necessary.
• If an `s2` character is not in `s1_differences`, increment the `unique_to_s2` variable by `1`.
5. Compute the number of deletions by looping over `s1_differences` and adding the value of each key with the value of `unique_to_s2`.
6. Return the number of deletions.

## Code solution

anagrams.js
``````function makingAnagrams(s1, s2) {
let unique_to_s2 = 0;
const s1_differences = {};

for(let i = 0; i < s1.length; i++) {
if (!s1_differences[s1[i]]) {
s1_differences[s1[i]] = 1;
} else {
s1_differences[s1[i]]++;
}
}

for (let i = 0; i < s2.length; i++) {
// character match with s1. One less difference.
if (s1_differences[s2[i]]) {
s1_differences[s2[i]]--;
} else { // no character match with s1.
unique_to_s2++;
}
}

let total_s1_differences = Object.values(s1_differences).reduce((a, b) => a + b, 0);
}
``````

## Test cases

Let's test the `makingAnagrams` function above.

The first test case will use strings `cde` and `abc`. The number of deletions to make these two strings anagrams is `4`. The deletion of characters `de` in the first string and the deletion of characters `ab` in the second string results in a total of four deleted characters.

``````console.log(makingAnagrams('cde', 'abc')); // 4
``````

The `makingAnagrams` function returns the correct value of `4` for the above test case.

The next test case will use strings `abc` and `amnop`. The number of deletions to make these two strings anagrams is `6`. The deletion of characters `bc` in the first string and the deletion of characters `mnop` in the second string results in a total of six deleted characters.

``````console.log(makingAnagrams('abc', 'amnop')); // 6
``````

The `makingAnagrams` function returns the correct value of `6` for this test case.

## Time and space complexity

The Big O time complexity of the solution is linear, or `O(m + n)`, where `m` is the length of string `s1` and `n` is the length of string `s2`. The solution used two loops that iterated across the entire length of characters in each string.

The Big O space complexity of the solution is linear, or `O(n)`, where `n` is the length of the string `s1`. The solution stores each character of the string `s1` as a key in the `s1_differences` object.