242. Valid Anagram

In this tutorial we will solve 242. Valid Anagram problem from leetcode.

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 242. Valid Anagram problem

Problem statement

In this problem we are given two strings s and t. We have to return true if t is an anagram of s. If they are not anagram then we will return false.

Example from leetcode.

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Constraints:

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.

In example 1, we can see that both string s and t are anagram, they have same number of letters and letters are used exact number of times in both the strings. Thus we will return true.

In example 2, we will return false because even though they are of same length but uses different letters.

Approach

To solve this problem we will have to keep track of the number of times each letter appears in string s and in string t. We can save the letter frequency in a hash map. Finally, at the time of comparing if the hash map frequencies matches then we have an anagram, otherwise we do not have an anagram.

This is how the steps will look like if we consider the following input string s = "anagram", t = "nagaram".

hashmap = {}

s = a n a g r a m
    ^
a is not present in the hash map, make new entry.
hashmap = {
  a: 1
}


s = a n a g r a m
      ^
n is not present in the hash map, make new entry.
hashmap = {
  a: 1,
  n: 1
}


s = a n a g r a m
        ^
a is present in the hash map, increment the entry.
hashmap = {
  a: 2,
  n: 1
}


s = a n a g r a m
          ^
g is not present in the hash map, make new entry.
hashmap = {
  a: 2,
  n: 1,
  g: 1
}


s = a n a g r a m
            ^
r is not present in the hash map, make new entry.
hashmap = {
  a: 2,
  n: 1,
  g: 1,
  r: 1
}


s = a n a g r a m
              ^
a is present in the hash map, increment the entry.
hashmap = {
  a: 3,
  n: 1,
  g: 1,
  r: 1
}


s = a n a g r a m
                ^
m is not present in the hash map, make new entry.
hashmap = {
  a: 3,
  n: 1,
  g: 1,
  r: 1,
  m: 1
}

We have prepared the hash map for string s. Now we will go through the letters of string t and subtract the letter's frequencies from the hash map. If we encounter a letter from string t that has no entry in the hash map then we can conclude that the given strings s and t are not anagram.

hashmap = {
  a: 3,
  n: 1,
  g: 1,
  r: 1,
  m: 1
}


t = n a g a r a m
    ^
n is present in the hash map, decrement the entry.
hashmap = {
  a: 3,
  n: 0,
  g: 1,
  r: 1,
  m: 1
}


t = n a g a r a m
      ^
a is present in the hash map, decrement the entry.
hashmap = {
  a: 2,
  n: 0,
  g: 1,
  r: 1,
  m: 1
}


t = n a g a r a m
        ^
g is present in the hash map, decrement the entry.
hashmap = {
  a: 2,
  n: 0,
  g: 0,
  r: 1,
  m: 1
}


t = n a g a r a m
          ^
a is present in the hash map, decrement the entry.
hashmap = {
  a: 1,
  n: 0,
  g: 0,
  r: 1,
  m: 1
}


t = n a g a r a m
            ^
r is present in the hash map, decrement the entry.
hashmap = {
  a: 1,
  n: 0,
  g: 0,
  r: 0,
  m: 1
}


t = n a g a r a m
              ^
a is present in the hash map, decrement the entry.
hashmap = {
  a: 0,
  n: 0,
  g: 0,
  r: 0,
  m: 1
}


t = n a g a r a m
                ^
m is present in the hash map, decrement the entry.
hashmap = {
  a: 0,
  n: 0,
  g: 0,
  r: 0,
  m: 0
}

We reached the last letter of string t and we never encountered any letter that is not present in the hash map. Hence both the strings are anagram and we will return true.

Let us look at example 2 having input string s = "rat", t = "car"

hashmap = {}

s = r a t
    ^
r is not present in the hash map, make new entry.
hashmap = {
  r: 1
}


s = r a t
      ^
a is not present in the hash map, make new entry.
hashmap = {
  r: 1,
  a: 1
}


s = r a t
        ^
t is not present in the hash map, make new entry.
hashmap = {
  r: 1,
  a: 1,
  t: 1
}

Now we will look at the letters of string t.

hashmap = {
  r: 1,
  a: 1,
  t: 1
}


t = c a r
    ^
c is not present in the hash map, input strings are not anagram, exit.

Code

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  if (s.length !== t.length) return false;

  let hm = new Map();
  for(let ch of s) {
    if (hm.has(ch)) hm.set(ch, (hm.get(ch) || 0) + 1);
    else hm.set(ch, 1)
  }

  for(let ch of t) {
    const frequency = hm.get(ch);
    if (!frequency) return false;
    hm.set(ch, frequency - 1);
  }

  return true;
};

Complexity

Time complexity: O(n)

In the first loop we go through all the letters of string s. Hence, if we have n letters then we will loop n times. Therefore, time complexity for the first loop will be O(n).

Next, we loop through all the letters of string t. In the worst case we have to go through all the letters and check them in the hash map. So, the second loop will also iterate n times. Therefore, time complexity for the second loop will be O(n).

Since we have the two loops and their individual time complexities is O(n) so, the final time complexity will be O(n) + O(n) i.e., O(2n) which is O(n).

Space complexity: O(n)

In the worst case, our hash map will save n elements. Thus the space complexity will be O(n).