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

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);
  return total_s1_differences + unique_to_s2;
}

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.