CODEWITHSUNDEEP
javascripttime-complexitycomputer-scienceanagram
DGwang
DGwang

Reputation: 157

Time Complexity for JavaScript Anagram Function

I had an assignment to right a function that will take 2 strings and return the number of characters needed to be deleted in order to make the 2 strings anagrams of each other. My question is what the time complexity of this function is and if there is a faster way to achieve the same result. Here is my solution:

function anagramDelete(str1, str2){
    let obj1 = {}, obj2 = {};

    // Load obj1 with all characters of str1 and their count
    str1.split('').forEach((char)=> {
        if(char in obj1){
            obj1[char]++;
        } else {
            obj1[char] = 1;
        }
    });

    // Load obj2 with all characters of str1 and their count
    str2.split('').forEach((char)=> {
        if(char in obj2){
            obj2[char]++;
        } else {
            obj2[char] = 1;
        }
    });

    // Track # of chars deleted
    let numOfDeletions = 0;

    // Compare each char in obj1 w obj2 and count deletions
    for(char in obj1){
        if(obj2[char]){
            numOfDeletions += Math.abs(obj2[char] - obj1[char]);
        } else {
            numOfDeletions += obj1[char];
        }
    }
    // Compare each char in obj2 w obj1 and count deletions
    for(char in obj2){
        if(!obj1[char]){
            numOfDeletions += obj2[char];
        }
    }
    return numOfDeletions;
}

As far as I can tell, because there are 4 loops it would be O(4n) or just O(n). I say this because there are no nested loops. Is this correct? Any better solutions?

Upvotes: 0

Views: 554

Answers (3)

Jonas Wilms
Jonas Wilms

Reputation: 138277

Not better but shorter:

  function anagramDelete(str1, str2){
   const chars = {};
   var result = 0;

   for(const char of str1)
     chars[char] = (chars[char] || 0) +1;

   for(const char of str2)
     chars[char] = (chars[char] || 0) -1;

   for(const [char, count] of Object.entries(chars))
    result += Math.abs(count);

   return result;
 }

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386654

You could use a single object and sum only the absolut values.

This solution uses the strings as array like objects.

function anagramDelete(str1, str2) {
    var letters = {};

    Array.prototype.forEach.call(str1, char => letters[char] = (letters[char] || 0) + 1);
    Array.prototype.forEach.call(str2, char => letters[char] = (letters[char] || 0) - 1);
 
    return Object.keys(letters).reduce((r, k) => r + Math.abs(letters[k]), 0);
}

console.log(anagramDelete('anagram', 'function'));

Upvotes: 1

Ely
Ely

Reputation: 11162

Your code is O(n + m); in general one does not really care too much about constants in a complexity class. n is the length of the first string and m is the length of the second string.

Also: To be precise in your case, since you mentioned O(4n) - I am not sure if that is accurate. You use the split function twice, which turns a string into an array of characters in your case. You did not account for that in your analysis.

O(n + m) would be the correct answer.

And if you want to detail the analysis it would be O(3n + 3m). That is because:
- for the first string you use split (O(n)), you loop over each character (O(n)) and you loop again for comparison (O(n))
- for the second string you use split (O(m)), you loop over each character (O(m)) and you loop again for comparison (O(m))

I assume your code is correct. I did not check that.

P.S.:
If you are interested in fine tuning the constants you can refer to the other answers, they are probably faster than your code in theory. In practice I don't think that matters really.

Upvotes: 0

Related Questions