Problem Statement #

Given two strings s and t, write a function to determine if t is an anagram of s.

Examples #

Example 1:

• Input: s = "anagram", t = "nagaram"
• Output: true

Example 2:

• Input: s = "rat", t = "car"
• Output: false

Solution #

var isAnagram = function(s, t) {
    // Early return if lengths differ
    if (s.length !== t.length) {
        return false;
    }

    let s1 = s.split('').sort();
    let s2 = t.split('').sort();

    // Compare arrays
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] !== s2[i]) {
            return false;
        }
    }

    return true;
};

Understanding Anagrams #

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. In other words, two strings are anagrams if they contain the same characters with the same frequencies, just in a different order.

Examples of Anagrams #

✓ "anagram" and "nagaram" are anagrams
  You can rearrange "anagram" to form "nagaram"

✗ "rat" and "cat" are NOT anagrams
  "rat" doesn't contain the letter 'c'

Approach Analysis #

Key Insight: Length Check #

If two strings have different lengths, they cannot be anagrams. This is because anagrams must use all original letters exactly once. A longer string would have leftover characters that couldn’t be matched in the shorter string.

Sort and Compare Method #

The primary approach used in this solution is the sort and compare method:

1. Check if lengths are equal (early return optimization)
2. Split both strings into character arrays
3. Sort both arrays alphabetically
4. Compare the sorted arrays element by element

This approach has a time complexity of O(n log n) due to the sorting operation.

Code Breakdown #

Step 1: Early Length Check #

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

This optimization avoids unnecessary splitting and sorting operations when we can immediately determine the strings cannot be anagrams.

Step 2: Split and Sort #

let s1 = s.split('').sort();
let s2 = t.split('').sort();

The split('') method separates each character into its own array element. The sort() function performs lexicographic sorting. For example:

• "anagram".split('') produces ['a', 'n', 'a', 'g', 'r', 'a', 'm']
• After sorting: ['a', 'a', 'a', 'g', 'm', 'n', 'r']

Step 3: Compare Arrays #

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

This loop compares each element position-by-position. If any mismatch is found, we immediately return false.

Alternative Approach: Character Frequency Map #

A more efficient approach uses a hash map to count character frequencies:

var isAnagram = function(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const charCount = new Map();

    // Count characters in first string
    for (let char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }

    // Decrement counts using second string
    for (let char of t) {
        if (!charCount.has(char)) {
            return false;
        }
        charCount.set(char, charCount.get(char) - 1);
        if (charCount.get(char) < 0) {
            return false;
        }
    }

    return true;
};

This approach has O(n) time complexity and O(1) space complexity (assuming a fixed character set like lowercase English letters, which has at most 26 unique characters).

When to use character counting over sorting:

The character counting method becomes particularly advantageous when:

• You need to compare one string against multiple other strings
• You’re working with very long strings (e.g., 2,000+ characters)
• You want optimal time complexity

Time and Space Complexity #

Sort and Compare Method #

Time Complexity: O(n log n)

• split(): O(n) - creates an array with n elements
• sort(): O(n log n) - JavaScript typically uses Timsort
• Loop comparison: O(n) - iterates through n elements
• Overall: O(n log n)

Space Complexity: O(n)

• Two arrays to hold characters from both strings

Hash Map Method #

Time Complexity: O(n)

• Two passes through the strings

Space Complexity: O(1)

• At most 26 characters for lowercase English letters (constant space)

Conclusion #

The Valid Anagram problem demonstrates important concepts in string manipulation and algorithm design. The sort-and-compare approach provides a clean, intuitive solution that’s easy to understand and implement, while the hash map approach offers better time complexity for performance-critical applications.

For interviews, being able to discuss both approaches and their trade-offs demonstrates strong understanding of algorithmic complexity and problem-solving flexibility.