Valid Anagram Space Complexity

Question

var isAnagram = function(s, t) {
const len = s.length;
if (len !== t.length) return false;
const hashTab = {};
for (let i = 0; i < len; i++) {
    if (!hashTab[s[i]]) {
        hashTab[s[i]] = 1;
    } else {
        hashTab[s[i]]++;
    }
    if (!hashTab[t[i]]) {
        hashTab[t[i]] = -1;
    } else {
        hashTab[t[i]]--;
    }
}
for (let item in hashTab) {
    if (hashTab[item]) return false;
}
return true;

Having a hard time figuring out the space complexity of this algorithm. My hypothesis is O(n) as the hashtable grows in size in relations to the input s. This question assumes that the string only contains lowercase letters.

Maybe I'm misunderstanding, but, if the strings only contain lowercase letters, then there are only 26 possible unique keys in `hashTab`, so the maximum size of `hashTab` is 26 key-value pairs, right? Assuming that we used fixed-bit counts as the values, that gives **constant**-bounded auxiliary space usage (or, if counts are arbitrarily many bits, the size of the counts is logarithmic so the overall space usage would be logarithmic). — Ollin Boer Bohan, Jul 11 '18 at 23:56
Agreed, it is O(n) with respect to the length of the strings, but bounded by the size of the alphabet (e.g. 26 if the alphabet is [a-z], considerably more if the alphabet is all Unicode characters) — John Hascall, Jul 12 '18 at 09:11

score 0 · Answer 1 · answered Jul 12 '18 at 11:00

As you mentioned that the string only contains lowercase letters, we can convert characters in given string into corresponding integers ranging from 0 to 25.
To keep track of frequencies of these letters we can declare an array of exactly 26 size space. So, overall space complexity will be O(M), where M is total different letters. In this case, M=26. So, space complexity is O(26).

var isAnagram = function(s, t) {
  const len = s.length;
  if (len !== t.length) return false;
  hashTab = new Array(26);
  for(i = 0; i<26; i++){
     hashTab[i] = 0;
  }
  for (let i = 0; i < len; i++) {
     idx = s[i].charCodeAt()-97; 
     hashTab[ idx ]++;
     idx = t[i].charCodeAt()-97; 
     hashTab[ idx ]--;
  }
  for(i = 0; i<26; i++){
     if(hashTab[i]!=0) return false;
  }
  return true;
}

Danny_ds · Answer 2 · 2018-07-13T20:52:20.637

0

Since the used space is constant (26 letters/items in this case - or even if you used an array of 256 items) and not dependent on the length of the input(s), space complexity is O(1).

Also see this answer.

edited Jul 13 '18 at 20:52

answered Jul 13 '18 at 20:44

Danny_ds

11,201
1
24
46

score 0 · Answer 3 · answered Jul 13 '18 at 20:44

The major space cost in your code is the hashmap which may contain a frequency counter for each lower case letter from a to z. So in this case, the space complexity is supposed to be constant O(26).

To make it more general, the space complexity of this problem is related to the size of alphabet for your input string. If the input string only contains ASCII characters, then for the worst case you will have O(256) as your space cost. If the alphabet grows to the UNICODE set, then the space complexity will be much worse in the worst scenario.

So in general its O(size of alphabet).

Valid Anagram Space Complexity

3 Answers3