Leetcode 242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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<sup>4</sup>

• s and t consist of lowercase English letters.

Thinking process

It is straightforward to consider sorting in JavaScript. By sorting the two strings, we can compare them to check if they are the same. If they are identical, we return true; otherwise, we return false.

However, it's important to note that the time and space complexity of the sorting algorithm cannot be guaranteed, as it depends on the implementation used by different browsers. On average, merge sort or quicksort, which are commonly used by browsers, have a time complexity of O(n log n).

Another approach is to utilise a hashmap data structure, which can also be effective. We can store each character of the strings as keys in the map, with their occurrences as values. By comparing the character occurrences in both strings, we can determine if they are anagrams.

Algorithm

1. Check if the lengths of both strings are the same; if not, return false.

2. Initialise a map using a hash map.

3. Loop through string 's' to store all characters as keys and the number of occurrences of each character as values.

4. Loop through string 't':

   • Check if each character exists. If not, return false.

   • If the character in 't' exists in 's', decrease the count of that character.

   • If the count of the character in the map is less than 0, return false.

   • If none of the conditions above are met, return true.

Implementation

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if (s.length !== t.length) return false
    let map = new Map();
    for (let char of s) {
       map.set(char, (map.get(char) || 0) + 1 );
        };

    for (let char of t) {
        if (!map.has(char)) return false;
        map.set(char, map.get(char) - 1);
        if(map.get(char) < 0) return false;
        }
    return true;
    }

Time & space complexity Analysis

The time complexity of this implementation is O(n), where n is the length of the input strings s and t. This is because we iterate through each character of both strings exactly once.

The space complexity is also O(n) because we use a map to store the counts of characters in string s, and in the worst case scenario, the map will contain all unique characters of string s, which would be of size n.

Conclusion

In summary, both sorting the strings and utilising a hashmap approach are effective methods for determining if two strings are anagrams in JavaScript.

1. Sorting the strings presents a straightforward solution. After sorting, comparing the strings directly allows for a quick assessment of their anagram status. However, it's important to consider the potential variability in time and space complexity depending on the sorting algorithm's implementation.

2. Alternatively, employing a hashmap data structure enables efficient tracking of character occurrences in both strings. By comparing these occurrences, we can confidently establish whether the strings are anagrams. This method consistently maintains a time complexity of O(n) and a space complexity of O(n), ensuring reliable performance.

Ultimately, the choice between these approaches may depend on various factors, including string size, performance requirements, and personal preference.