educative.io

Educative

Time complexity of the solution

The time complexity of the solution is reported as “O(N+M), where ‘N’ and ‘M’ are the number of characters in the input string and the pattern, respectively.”

However, the JS solution contains a call to Object.keys(charFrequency) in each iteration of a for-loop. From what I can tell, calling Object.keys() is an O(M) operation: javascript - Object.keys() complexity? - Stack Overflow

for (windowEnd = 0; windowEnd < str.length; windowEnd++) {
    ...
    if (matched === **Object.keys(charFrequency)**.length) {
      return true;
    }
    ...
}

Wouldn’t that make the overall time complexity O(N*M)?