LeetCode 242: Valid Anagram – JavaScript Solution

📌 Introduction

In this post, we’ll solve LeetCode 242: Valid Anagram. We’ll cover a brute force sorting approach and two optimized solutions using frequency counters (an array and a HashMap). We'll also analyze the time and space complexities for each. All code examples are in JavaScript.

👉 Original problem link: LeetCode – 242. Valid Anagram

---

1. Problem Overview

The task is to write a function that takes two strings, s and t, as input. It should 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.

---

2. Examples

Example 1:

Input: s = "anagram", t = "nagaram" Output: true Explanation: The string t is a direct rearrangement of the characters in the string s.

Example 2:

Input: s = "rat", t = "car" Output: false Explanation: The characters in s and t are different, so one cannot be formed by rearranging the other.

---

3. Approaches

🔹 Approach #1: Brute Force (Sorting)

• Idea: The most straightforward way to check for an anagram is to sort both strings alphabetically. If the two strings are anagrams of each other, they will become identical once sorted. We can then simply compare the sorted strings.

Code (JavaScript):

JavaScript

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

    //O(N.log(N))
    const sort = str => str.split('').sort().join('')

    return sort(s) == sort(t)
};

• Time Complexity: O(N*log(N)) - Dominated by the sorting operation on the strings.

• Space Complexity: O(1) - We are not using auxiliary data structures that scale with the input size.

---

🔹 Approach #2: Optimized (Frequency Counter Array)

• Idea: Since the problem constraints mention that the strings consist only of lowercase English letters, we can use a fixed-size array of 26 elements as a frequency counter. We iterate through string s to increment the count for each character and then iterate through string t to decrement the counts. If the strings are anagrams, all counts in the array will be zero at the end.

Code (JavaScript):

JavaScript

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

    //counter array for lowercase letters-only
    const counts = new Array(26).fill(0)

    for (let i = 0; i < s.length; i++) {
        const index = s.charCodeAt(i) - 'a'.charCodeAt(0) //gives 0 based index for lowercase letters
        counts[index]++
    }

    for (let i = 0; i < t.length; i++) {
        const index = t.charCodeAt(i) - 'a'.charCodeAt(0) //gives 0 based index for lowercase letters
        counts[index]--
        if (counts[index] < 0) return false //early edge case - extra character found
    }

    for (let i = 0; i < counts.length; i++) {
        if (counts[i] !== 0) return false
    }

    return true
};

• Time Complexity: O(N) - We iterate through both strings once.

• Space Complexity: O(1) - The counts array has a constant size of 26, regardless of the input string length.

---

🔹 Approach #3: Optimized (HashMap for Unicode Characters)

• Idea: As a follow-up, if the input strings could contain any Unicode characters, a fixed-size array would not work. A HashMap is the perfect tool for this scenario. We first populate the map with character frequencies from string s. Then, we iterate through string t, decrementing the count for each character. If we encounter a character not in the map or if a count goes below zero, they are not anagrams.

Code (JavaScript):

JavaScript

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

    //frequency map - handles any unicode
    const map = new Map()

    for (let i = 0; i < s.length; i++) {
        const c = s[i]
        if(!map.has(c)){
            map.set(c, 0)  //initialising frequency for new character
        }
        map.set(c, map.get(c) + 1)  //increment frequency
    }

    for (let i = 0; i < t.length; i++) {
        const c = t[i]
        if(!map.has(c)){
            return false    //extra character found
        }

        map.set(c, map.get(c) - 1)  //increment frequency
        if(map.get(c) < 0) return false //early exit
    }

    for (const [letter, count] of map) {
        if (count !== 0) return false
    }

    return true
};

• Time Complexity: O(N) - We iterate through both strings once.

• Space Complexity: O(N) - In the worst case, if all characters in s are unique, the map will store N key-value pairs.

---

4. Key Takeaways

• ✨ Anagram problems are fundamentally about matching character frequencies.

• ✨ For a limited character set (like lowercase English letters), a fixed-size array is a highly efficient, O(1) space solution.

• ✨ For a general-purpose solution that supports any character (including Unicode), a HashMap is the most flexible and robust approach, trading constant space for linear space O(N).