Problem statement

You are tasked with determining whether two given strings, s and t, are anagrams of each other. An anagram is a word or phrase created by rearranging the letters of another word or phrase, using all the original letters exactly once. Your goal is to implement a function that returns true if t is an anagram of s, and false otherwise.

Constraints

1. Strings s and t consist of lowercase English letters.

First Thoughts

Upon initial consideration, the problem requires comparing two strings to determine if one can be formed by rearranging the letters of the other. To solve this, you may want to explore efficient ways of checking for anagram conditions, possibly involving character frequency counts or sorting. The constraints suggest that the solution should be optimized for larger input sizes, so an algorithm with a time complexity less than O(n^2) would be preferable.

By taking the first thoughts into account, we can come up with a few possible solutions:

1. Sort the strings and compare them
2. Use a HashMap to store the frequency of each character in the strings and compare the hash tables

Solution

Solution 1: Sort the strings and compare them

var isAnagram = function (s, t) {
  // Sort the characters in the strings
  const sortedStr1 = s.split("").sort().join("")
  const sortedStr2 = t.split("").sort().join("")
 
  // Compare the sorted strings
  return sortedStr1 === sortedStr2
}

In above method, the isAnagram function takes two strings as input, sorts the characters in both strings, and then compares the sorted strings. If the sorted strings are equal, the function returns true, indicating that the strings are anagrams; otherwise, it returns false.

1. Time Complexity

Sorting involves a time complexity of O(n log n), where n is the length of the strings. The split and join operations have a time complexity of O(n), where n is the length of the strings. Therefore, the overall time complexity of the code is dominated by the sorting operation, making it O(n log n).

2. Space Complexity

The space complexity is primarily determined by the space needed for the sorted strings. Each split and join operation creates a new array or string, resulting in an auxiliary space of O(n) for each string. The sortedStr1 and sortedStr2 strings contribute to the space complexity. Therefore, the overall space complexity of the code is O(n).

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Using the sorting approach for checking anagrams has both upsides and downsides:

1. Upsides:

• Simplicity: The sorting approach is relatively simple and easy to understand. The logic involves just a few lines of code.

• Consistent Results: The approach is robust and gives consistent results. It works for any pair of anagrams, regardless of the language or the character set used.

• Efficiency for Short Strings: For short strings, the performance overhead of sorting is not significant, and the simplicity of the algorithm can be an advantage.

2. Downsides:

• Efficiency for Long Strings: Sorting has a time complexity of O(n log n), where n is the length of the string. For very long strings, especially in performance-critical applications, this approach might not be the most efficient.

• Case Sensitivity and Spaces: The current implementation is case-insensitive and ignores spaces. While this may be desirable in some cases, it might not suit all scenarios. Modifying the implementation to handle different requirements could increase its complexity.

• Loss of Original Order: The sorting approach discards the original order of characters in the string. If preserving the order is important (e.g., for certain anagram-related applications), then this method may not be suitable.

• Algorithmic Overhead: Sorting involves a certain amount of algorithmic overhead. For short strings or infrequent usage, this may not be a significant concern. However, in scenarios where the anagram check is performed frequently or on large datasets, more optimized algorithms may be considered.

Solution 2: Using HashMap

var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
 
  const counter = new Map()
 
  for (let char of s) {
    counter.set(char, (counter.get(char) || 0) + 1)
  }
 
  for (let char of t) {
    if (!counter.has(char) || counter.get(char) === 0) {
      return false
    }
    counter.set(char, counter.get(char) - 1)
  }
 
  return true
}

In above method, we have gone through these steps:

1. Check Lengths

If the lengths of strings s and t are not equal, return False.

if (s.length !== t.length) {
        return false;
    }

2. Count Characters in s

• Create a dictionary counter to store the count of each character in string s.
• Loop through each character char in string s.
• Use counter.get(char, 0) to retrieve the current count of char in the dictionary. If char is not in the dictionary, default to 0.
• Increment the count of char in the dictionary by 1.

const counter = new Map()
 
for (let char of s) {
  counter.set(char, (counter.get(char) || 0) + 1)
}

3. Check Characters in t

• Loop through each character char in string t.
• Check if char is not in the counter dictionary or if its count is already 0. If either condition is met, return False.
• Decrement the count of char in the dictionary by 1.

for (let char of t) {
        if (!counter.has(char) || counter.get(char) === 0) {
            return false;
        }
        counter.set(char, counter.get(char) - 1);
    }

1. Time Complexity

The code iterates through both input strings once, so the time complexity is O(n), where n is the length of the strings. The Map operations (set, get, has) have an average time complexity of O(1), making the overall time complexity linear. Therefore, the time complexity of the code is O(n).

2. Space Complexity

The code uses a Map (counter) to store the count of each character. In the worst case, where all characters are distinct, the size of the Map is proportional to the length of the input strings, leading to a space complexity of O(n), where n is the length of the strings.

• Time Complexity: O(n)
• Space Complexity: O(n)

Using the HashMap approach for checking anagrams has both upsides and downsides:

1. Upsides:

• Linear Time Complexity: The HashMap approach has a linear time complexity of O(n), where n is the length of the strings. This is efficient, especially for longer strings, as it avoids the O(n log n) time complexity associated with sorting.

• Character Count Preservation: This approach preserves the count of each character, providing more information than just checking if two strings have the same set of characters. This can be useful in certain scenarios where knowing the count of each character is relevant.

• Flexible Data Structure: A HashMap provides flexibility and extensibility. It can be easily adapted to handle more complex requirements, such as tracking character positions, Unicode characters, or handling case sensitivity.

2. Downsides:

• Space Complexity: In the worst case, where all characters are distinct in both strings, the space complexity is O(n), where n is the length of the strings. While this is generally reasonable, it may lead to increased memory usage for very long strings.

• Overhead of Map Operations: While Map operations (set, get, has) generally have an average time complexity of O(1), there is still a slight overhead associated with using a more complex data structure compared to simple array indexing.

• Potential for Hash Collisions: In certain scenarios, if there are many distinct characters and a hash collision occurs, the accuracy of the anagram check might be compromised. However, the likelihood of hash collisions is typically low with a well-designed hash function.

Here is version of this approach without using the Map so that the approach is applicable to all languages:

var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
 
  const counter = {}
 
  for (let char of s) {
    counter[char] = (counter[char] || 0) + 1
  }
 
  for (let char of t) {
    if (!counter[char] || counter[char] === 0) {
      return false
    }
    counter[char]--
  }
 
  return true
}

Here is another version of it for reference:

var countCharacterOccurrences = function (str) {
  var charCount = {}
 
  for (var i = 0; i < str.length; i++) {
    var char = str[i]
 
    if (charCount[char]) {
      charCount[char]++
    } else {
      charCount[char] = 1
    }
  }
 
  return charCount
}
 
var isAnagram = function (s, t) {
  const firstCharCount = countCharacterOccurrences(s)
  const secondCharCount = countCharacterOccurrences(t)
 
  for (var char in firstCharCount) {
    if (firstCharCount[char] !== secondCharCount[char]) {
      return false
    }
  }
 
  for (var char in secondCharCount) {
    if (!firstCharCount[char]) {
      return false
    }
  }
 
  return true
}

Have fun coding! 😎 and see you in the next exercise.