Hackerrank "Strings: Making Anagrams" Javascript Solution

Question

This is the original problem :

Input Format

The first line contains a single string, a. The second line contains a single string, b.

Constraints

1<= |a|,|b| <= 10^4

It is guaranteed that and consist of lowercase English alphabetic letters (i.e., through ). Output Format

Print a single integer denoting the number of characters you must delete to make the two strings anagrams of each other.

Sample Input

cde

abc

Sample Output

4

Explanation

We delete the following characters from our two strings to turn them into anagrams of each other:

Remove d and e from cde to get c. Remove a and b from abc to get c. We must delete characters to make both strings anagrams, so we print on a new line.

And this is the solution I've came up with using javascript. I've decided to use objects in order to avoid nested for loops which leads to O(M*N). I think my solution is O(M+N+O+P), however, I do believe there's a much better solution out there, and some more refactoring can be done to my code. Anyone?

There are some default I/O codes you may find in the original website

function main() {
  var a = readLine();
  var b = readLine();

  // Creating object with {"k": 5, "a": 2, "b": 1} for example
  var objA = countAlphabetFrequency(a);
  var objB = countAlphabetFrequency(b);

  var numOfDeletionsA = countNumberOfDeletions(objA,objB);
  var numOfDeletionsB = countNumberOfDeletions(objB,objA);

  console.log(numOfDeletionsA + numOfDeletionsB);
}

function countAlphabetFrequency (arrOfAlphabets){
    var resultObj = {}

    for (i = 0; i < arrOfAlphabets.length; i++) {
        if (resultObj[arrOfAlphabets[i]]) {
          resultObj[arrOfAlphabets[i]] += 1;
        } else {
          resultObj[arrOfAlphabets[i]] = 1;
        }
    }
    return resultObj;
}

function countNumberOfDeletions (mainObj, referenceObj){
    var numOfDeletions = 0;

    for (var k in mainObj) {
        if (mainObj.hasOwnProperty(k)) {
          if (mainObj[k] && referenceObj[k]) {
            // Alphabet k exists in both strings
            if (mainObj[k] > referenceObj[k]) {
              // Main string has more k than in reference string
              numOfDeletions += mainObj[k] - referenceObj[k];
              mainObj[k] = referenceObj[k];
            }
          } else {
            // Alphabet k only exists in Main string
            numOfDeletions += mainObj[k];
          }
        }
    }

    return numOfDeletions
}

Answer 1

I like your idea of counting character frequencies first. This allows you to count the required deletions in linear time.

Your code is readable, but readability can be improved by more semantic naming and leveraging modern JavaScript language features.

Naming:

Regarding the variable names a, objA, mainObj, resultObj, arrOfAlphabets: Those identifiers mainly include type information (obj, arrOf). But as a reader, I am more interested in the role of your variables instead of their type. So instead of objA I would prefer to read frequenciesA or even freqA. And instead of arrOfAlphabets I suggest the simpler characters.

For-loops:

First of all, you probably forgot to declare the local loop iterator in for (i = 0; ...). Unfortunately, those omissions can introduce very hard to trace bugs as you now access and potentially share a global variable i.

Also, JavaScript arrays and strings implement the iterable protocoll. This means you can iterate over them using a simpler for-of loop:

for (let char of characters) { ... }

This allows you to replace arrOfAlphabets[i] with the more readable char.

Default properties:

There is a pretty common technique used to handle default values of object properties. Replace

if (obj[arrOfAlphabets[i]]) {
  resultObj[char] += 1;
} else {
  resultObj[char] = 1;
}

with the shorter and idiomatic

resultObj[char] = (resultObj[char] || 0) + 1;

Enumerate object keys:

Instead of

for (var k in mainObj) {
    if (mainObj.hasOwnProperty(k)) { ... }
}

you can nowadays use Object.keys to write

for (let key of Object.keys(mainObj)) { ... }

Refactoring:

You probably noticed the redundancy in

var numOfDeletionsA = countNumberOfDeletions(objA,objB);
var numOfDeletionsB = countNumberOfDeletions(objB,objA);
console.log(numOfDeletionsA + numOfDeletionsB);

If you modify your countAlphabetFrequency function to increment frequencies for string a and decrement frequencies for string b, you can simply sum the absolute frequencies to get the number of required deletions.

If you combine that with a more descriptive approach by replacing for-loops with forEach and reduce, you get a simpler implementation:

// Count character deletions required to make 'a' and 'b' anagrams:
function count(a, b) {
  let freqs = {};
  a.split('').forEach(char => freqs[char] = (freqs[char] || 0) + 1); // increment
  b.split('').forEach(char => freqs[char] = (freqs[char] || 0) - 1); // decrement
  return Object.keys(freqs).reduce((sum, key) => sum + Math.abs(freqs[key]), 0);
}

// Example:
console.log(count('ilovea', 'challenge')); // 9