const anagram = (str1, str2) => {
    str1 = str1.split('');
    str2 = str2.split('');
    
   let frequencyCounter1 = {};
   let frequencyCounter2 = {};

   for(let val of str1) {
       frequencyCounter1[val] = (frequencyCounter1[val] || 0)  1;
   }

    for(let val of str2) {
       frequencyCounter2[val] = (frequencyCounter2[val] || 0)  1;
   }

   for(let key in frequencyCounter1) {

       if(!(key in frequencyCounter2)) {
           return false;
       }

       if(frequencyCounter1[key] !== frequencyCounter2[key]) {
           return false;
       }
   }

    return true;
}

anagram('racecar', 'racecar');

This challenge asks to use a frequency counter pattern to test if str2 is an anagram of str1. The answer provided is supposedly O(n). How is this possible with this if statement:

if(!(key in frequencyCounter2)) {
           return false;
       }

Wouldn't this suggest you are going to loop through the object to make sure it contains that key, therefore you have nested loops and O(n^2)?

CodePudding user response：

it's actually O(n) because

for(let key in frequencyCounter1) {

       if(!(key in frequencyCounter2)) {
           return false;
       }

       if(frequencyCounter1[key] !== frequencyCounter2[key]) {
           return false;
       }
   }

you are iterating over frequencyCounter1 O(n) and then you find each iteration key from frequencyCounter1 in frequencyCounter2 and js objects are basically key-value pairs so finding a key will take O(1). hence the total time complexity is O(n)