Valid Anagram in JavaScript

Problem Statement :

“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. For example, “race” and “care” are anagrams of each other.

---

Approach 1: Sort and Compare

1. Given two strings s and t.

2. Base Case: compare the length of both strings s and t. If they are not equal then return false.

3. Sort the characters of both strings.

4. Compare the sorted strings. If they are equal, then the two strings are anagrams of each other. Otherwise, they are not.

// ES6 Arrow Function

const validAnagram = (s, t) => {
    // base case
    if(s.length !== t.length) return false;

    return s.split('').sort().join('') === t.split('').sort().join('');
}

Time Complexity: O(N * Log(N))

Space Complexity: O(N)

Note 1: Two strings cannot be anagrams if their lengths are not the same.

Note 2: The space complexity is O(N) as it takes O(string’s length) space, and the reason for this is that we generate a new array of size n when splitting the string.

---

Approach 2: Using Map Data Structure

1. Base Case: compare the length of both strings s and t. If they are not equal then return false.

2. Create a hash map.

3. Iterate through the first string and increment the count for each character in the hash map.

4. Iterate through the second string and check if the hash map contains the current character. If the hash map doesn’t have the character, return false. Otherwise, decrement the count for each occurrence of the character in the hash map.

5. After every decrement, check the count of each character in the hash map. If the count is 0, delete the character from the hash map.

6. Once the loop ends, check the size of the hash map. If the size of the hash map is 0, return true; otherwise, return false.”

// ES6 Arrow Function
const validAnagram2 = (s, t) => {
    // base case
    if(s.length !== t.length) return false;

    let map = new Map();

    for(let i of s) {
        map.set(i, map.get(i) + 1 || 1);
    }

    for(let i of t) {
        if(map.has(i)) {
            map.set(i, map.get(i)-1);
            if(map.get(i) == 0) map.delete(i);
        } else {
            return false;
        }
    }

    return map.size === 0;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Approach 3: Using Array as Buckets

1. Base Case: compare the length of both strings s and t. If they are not equal then return false.

2. Create a new array of size 26 using the Array() constructor and fill each element in the array with the value 0.

3. Iterate over the string S and keep track of the frequency of each character in the string in the array.

4. Then, iterate through the second string T and decrement the frequency of each character in the array.

5. Check if every value in the array is 0, and return true; Otherwise, return false.

// ES6 Arrow Function
const validAnagram = (s, t) => {
    if (s.length !== t.length) return false;

    const counts = new Array(26).fill(0);

    for (let i = 0; i < s.length; i++) {
        counts[s.charCodeAt(i) - 97]++;
        counts[t.charCodeAt(i) - 97]--;
    }

    return counts.every(count => count === 0);
}

Time Complexity: O(N)

Space Complexity: O(N)

---

I hope this article has provided you with valuable insights and helped you better understand the different approaches to solve this problem. Happy Coding!

---

Problem - Leetcode 242